计算复杂性对运筹学发展的影响

计算复杂性与运筹学的渊源很深。特别是,自解线性规划的Karmarkar算法出现以来,运筹学界谈论复杂性者越来越多。本文试图为这一趋势提供些注记。我们假定读者已阅读过[1]。一、复杂性理论从诞生起就与运筹学结下了不解之缘虽然计算复杂性理论是在可计算性理论的基础上发展起来的,但是运筹学的催生作用却无法忽视。当Edmonds在1965年提出多项式时间算法的概念时。