线性规划计算的复杂性

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