线性规划计算的复杂性

1979年11月7日,《纽约时报》第一版上刊出了一篇文章,开头就说“苏联无名数学家的新发现震动了数学和数值分析的世界”,还说这一发现可能应用到气象予报、工业规划、原油提炼、大工厂作业表设计、巡回路线问题和密码设计等方面。这样一个耸人听闻的新发现到底是怎么一回事呢?为什么它会有这样大的威力呢?这个新发现就是1979年1月《苏联科学院院刊》发表的一位年青学者哈强(Khachian)关于线性规划的椭球算法的研究报告。这个报告宣布了整系数线性规划不是一个NP完全问题。到目前为止,这个新发现还只是计算理论上的一个重要发现,还要做很多工作才能真正用于计算。