联合形式方法专业委员会：出版“不确定多项式时间”术语

此次发布用语新词：非确定性多项式时间( Nondeterministic Polynomial Time )。

非确定多项式时间

(非详细轮询时间)

作者：李国强(上海交通大学)。

开头指南这次增加了非确定多项式时间( Nondeterministic Polynomial Time )这个新术语。

非确定性多项式时间是一个复杂性问题，属于复杂性理论。

InfoBox :中文名称：非确定多项式时间

英文名： Nondeterministic Polynomial Time

缩写： NP

学科：计算复杂性理论的基本概述：又称NP问题，是一类非确定性图灵机在多项式时间内可以解决的判定问题。

也可以定义为可以通过确定性图灵机在多项式时间内验证答案是否正确的问题。

从定义上可以看出，确定性多项式时间问题(也称为p问题)属于非确定性多项式时间问题。 也就是说，p是NP的子集。

p和NP的两个集合相等吗？=NP问题(的结论尚不清楚，是数学、计算机科学领域的一大难题。

一些不确定性多项式时间问题中还有一类问题彼此等价，共同刻画了不确定性多项式时间问题中最难的一类问题。

这些是非确定性多项式时间完备问题( NP-complete，也称为NPC问题)。

所有的NP问题都可以在多项式时间内规定为任意的NPC问题。

在p和NPC都没有一个NP问题的情况下，我们称为非确定性多项式中间问题( NP-intermediate，也称为NPI问题)。

拉德纳证明了如果p不等于NP，则NPI集合不是空的[1]。

研究人员一直试图在同样复杂性的假设下证明整数分解问题等自然计算问题是NPI。

发展历程： 1936年，图灵建立了理论计算模型——图灵机[2]。

随着计算机在20世纪40年代和50年代的发展，图灵机被证明是正确的计算理论模型。

研究人员很快发现，基本图灵机无法解释计算机所需的时间和内存大小，但时间和空间在早期计算时代尤为重要。 20世纪60年代，哈特曼和斯特恩提出以输入长度为参数测量时间和空间长度函数，计算复杂度应运而生[3]。

随着研究者将高效计算定义为输入大小的多项式长，引出了非确定性多项式时间的完备性和NP问题。

20世纪70年代初期，库克和卡普的工作表明，许多组合和逻辑问题都是NPC问题[4-8]。

从那以后直到现在，这个问题已经成为计算机科学领域和数学领域的突出开放性问题。

后来兴起的电路复杂性、量子计算等理论领域，也为我们更好地理解p提供了很大的帮助吗？=NP问题这一计算机科学的宝物。

典型的例子：因为p问题是NP问题，所以所有具有多项式时间算法的问题都是NP问题。

图论上的最短路径问题、最小生成树问题、强连通部件问题、欧拉图问题等。

其他图论问题是NPC问题。

旅行商问题、哈密顿问题、独立集问题、顶点覆盖问题、群问题、图着色问题等。

数论问题中，素数判定问题于2004年由3位印度学者提出的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]的许多工具通过将各个问题约定为可满足性问题求解器来实现效率化。

参考文献

1.r.ladner.onthestructureofpolynomialtimereducibility.journaloftheacm.vol.22 (1) 155171，1975。

2.Alan turing.oncomputablenumbers.in proc.ofthelondonmathematicalsociety，1936。

3.hartmanisandr.Stearns.onthecomputationalcomplexityofalgorithms.transactionsoftheamericanmathematicalsociety，vol.vol

4.s.cook.thecomplexityoftheorem-proving procedures.in proc.of3rdacmsymp.theoryofcomputing，151，158，1971。

5.s.cook.ahierarchyfornondeterministictimecomplexity.journalofcomputerandsystemsciences，vol.7(4)，343-353，

6.s.cook.anoverviewofcomputationalcomplexity.communicationsoftheacm，vol.26(6):400-408，1983。

7.r.Karp.reducibilityamongcombinatorialproblems.incomplexityofcomputercomputations，85-104. Plenum Press，New York

8. R. Karp. Combinatorics，complexityandrandomness.communicationsoftheacm，vol.29(2)，98-109，1986。

9. M. Agrawal、N. Kayal、andn.sa xena.primesisinp.annalsofmathematicsvol.160 (2)、781-793和2004。

10.p.w.shor.algorithmsforquantumcomputation:discretelogarithmsandfactoring.in proc.of35 thannualsymposiumonfoundattion

11.r.m.karpreducibilityamongcombinatorialproblems.complexityofcomputercomputation，85103，1972。

12. Davis，Martin； Putnam，Hilary.acomputingprocedureforquantificationtheory.journaloftheacm，vol.7(3)，201215，1960。

13. Davis，Martin； Logemann，George； Loveland，Donald.amachineprogramfortheoremproving.communicationsoftheacm，vol.5(7) 394397，1961。

14. A. Biere，A. Cimatti，E. M. Clarke，Andy.Zhu.symbolicmodelcheckingwithoutbdds.in proc.of the5thinternationationationationalationals

15. E. M. Clarke，A. Gupta，o.ST richman.sat-basedcounterexample-guidedabstractionrefinement，ietransactionsonconconcon

16. J. Dolby，m，Vaziri，f.tip.findingbugsefficientlywithasatsolver，in proc.of the6 thjointmeetingoftheeeeuropeansoftwansoftwsolver

17. G. Katz、C. Barrett、D. L. Dill、K. Julian、m.j.kochenderfer.relu plex:anefficientsmtsolverververifyingdex

作者简介

上海交通大学李国强副教授li.g@sjtu.edu.cn的主要研究方向是形式化验证、程序语言理论、知识推理与验证术语工业委员会和术语平台介绍：计算机术语检定委员会( Committee on Terminology )的主要功能是

这对明确学科体系，开展科学研究，在全社会广泛传播科学和知识具有十分重要的意义。

术语平台CCFpedia的建设和不断优化，既能有效推进我国计算机术语的收集、检定、规范和传播，又能起到各个领域规范化标准定制的推动作用。

新版本的CCFpedia计算机术语平台http://term.ccf.org.cn )集成了术语的编辑运行和浏览使用，消除了旧版本跨平台操作的繁琐步骤，大大升级了接口

此外，新版平台通过引入知识图谱对所有术语数据进行了组织，并以图像多层关联的形式对术语浏览的应用形态进行了升级。

计算机术语检定工作委员会主任：刘挺(哈尔滨工业大学)副主任：王昊勇(同济大学)李国良)清华大学)主任助理：李一斌(上海海乂知信息科技有限公司)丁军)上海海乂知信息科技有限公司)林俊宇)中国科学院信息工程研究所)兰艳艳