联手形式化方法专业委员会：“非确定性多项式时间”术语发布 | CCF术语快线

InfoBox：

中文名：非确定性多项式时间

英文名：Nondeterministic Polynomial Time

简写：NP

学科：计算复杂性理论

基本简介：

亦称NP问题，是指一类判定问题，这些问题可以通过非确定性图灵机在多项式时间内被解决。也可以定义为可以通过确定性图灵机在多项式时间内验证答案是否正确的问题。由定义可知，确定性多项式时间问题（亦称P问题）属于非确定性多项时间问题，也即，P是NP的一个子集。P和NP两个集合是否相等（表示为P？=NP问题）的结论尚不被人们所知，是数学领域、计算机科学领域的重大难题之一。

非确定性多项式时间问题中还有一类型问题彼此等价，共同刻画了非确定性多项式时间问题中最难的一类问题。它们被称为非确定性多项式时间完备问题（亦称NP-complete，NPC问题）。所有NP问题都可以多项式时间规约至任意一个NPC问题。如果一个NP问题既不在P里也不在NPC里，我们称之为非确定性多项式中间问题（亦称NP-intermediate， NPI问题）。拉德纳证明了如果 P不等于NP，那么NPI集合非空 ^[1]。研究者一直试图证明在类似复杂性假设下，某些自然的计算问题是NPI的，例如整数分解问题等。

发展历程：

1936年，图灵建立了理论计算模型——图灵机 ^[2]。随着计算机在上世纪40年代和50年代的发展，图灵机被证明是正确的计算理论模型。研究者很快发现，基本图灵机无法解释计算机所需的时间或者内存大小，而时间与空间在早期的计算时代显得尤为重要，上世纪60年代，由哈特马尼斯和斯特恩斯提出以输入长度作为参数，测量时间和空间的长度函数，从而诞生了计算复杂性^[3]。随着研究者将高效计算定义为输入大小的多项式长度，引出了非确定性多项式时间完备性以及NP问题。上世纪70年代早期，库克和卡普的工作表明，大量的组合和逻辑问题是NPC问题^[4-8]。在此后直到现在，这个问题成为了计算机科学领域和数学领域的一个突出的开放性问题。在之后兴起的诸如电路复杂性、量子计算等理论领域，也极大地帮助我们更好地理解P？=NP问题这一计算机科学的瑰宝。

典型样例：

由于P问题属于NP问题，因此具有多项式时间算法的问题均属于NP问题。诸如图论上的最短路径问题、最小生成树问题、强连通部件问题、欧拉图问题等。而另外一些图论上的问题则属于NPC问题。诸如旅行商问题、哈密尔顿问题、独立集问题、顶点覆盖问题、团问题、图着色问题等。

在数论问题中，素数判定问题在2004年，由三位印度学者给出的AKS算法得出了素数测试一个多项式算法^[9]，该结论也获得了2006年的哥德尔奖。另外一个著名问题是整数分解问题，作为现代密码学的基础，虽然目前没有多项式时间的算法，但研究者认为它的判定问题版本（和原问题等价）不是NPC问题。随着量子计算的兴起，肖尔得出了大数因式分解的多项式时间的量子算法，动摇了现代密码学的根基^[10]。但它无法解决P？=NP问题。

在代数问题中，线性规划有着多项式时间的算法，然而整数规划则是NPC的。作为整数规划子问题，0-1方程组和子集和问题也是NPC的，还有一些问题本质上也是代数问题，如划分问题、背包问题等，它们也是NPC的。这些问题均属于NP问题。卡普第一个收集总结了21个NPC问题^[11]，在之后有许多学者热衷于总结NPC的问题，在经典的算法书籍中都会有此部分的详细讲述。

最后需要指出的是，并非NPC问题一定不存在实际中高效的算法，如可满足性问题（亦称SAT问题），作为NPC的第一个问题^[4]，它却有很高效的算法，被称为DPLL算法^[12,13]。同时存在高效的工具可满足性问题求解器。目前形式化验证^[14,15]、软件工程^[16]甚至深度学习^[17]的很多工具都是通过都将各自的问题规约至可满足性问题求解器来实现高效化。

参考文献