np完全问题是最难的题吗
2015-06-20 01:37:13
是的,是关于图论的一个数学问题,被列为七大数学难题之一。
NP完全问题是不确定性图灵机在P时间内能解决的问题,是世界七大数学难题之一[1]。NP的英文全称是Non-deterministic Polynomial的问题,即多项式复杂程度的非确定性问题。NP完全问题是NP类中“最难”的问题,也就是说它们是最可能不属于P类的。这是因为任何NP中的问题可以在多项式时间内变换成为任何特定NP完全问题的一个特例。属于计算机科学理论的一个基本概念。
阅读剩余内容