NP完全问题及有关的理论研究

当代计算机科学理论中,有一个有名的尚未解决的难题,叫作“P=NP”问题。从七十年代初期开始,发现了许多具体的问题,包括逻辑演算、图论、规划论等领域中的组合问题,它们都彼此等价;只要有一个得到解决,P=NP 问题就可得到解决。这就是所谓的 NP 完全问题。这篇文章是有关这个问题研究现状的一个综述。曾在去年长春“计算机科学署期讨论会”上宣读过,受到好评。这次发表,作者又作了一些修改。