非定常多项式（英语：non-deterministic polynomial，缩写：NP）时间复杂性类，或称非确定性多项式时间复杂性类，包含了可以在多项式时间内，对一个判定性算法问题的实例，一个给定的解是否正确的算法问题。
NP是计算复杂性理论中最重要的复杂性类之一。它包含复杂性类P，即在多项式时间内可以验证一个算法问题的实例是否有解的算法问题的集合；同时，它也包含NP完全问题，即在NP中“最难”的问题。计算复杂性理论的中心问题，P/NP问题即是判断对任意的NP完全问题，是否有有效的算法，或者NP与P是否相等。
形式化定义
复杂度类NP可以用NTIME来定义:：
NTIME(n ^ k )是决策问题的集合,可以解决的非确定性图灵机 O(n ^ {k )）次。
NP的理解
理解NP有两个角度：一个角度是作为确定性图灵机的一个推广，另一个角度是作为多项式时间可验证解的算法问题的集合。
NP困难问题和NP完全问题
要理解这几个概念，首先要明白几件事：
- 对于NP问题是否存在确定的多项式时间的解，目前还不清楚（即有可能有一天可以证明NP问题=P问题，但目前还证明不出来、也不能证明NP问题≠P问题，目前的结论只是NP问题集⊇P问题集
- 问题之间可以规约，即如果某个NP问题存在确定的多项式时间解，那么另一个NP问题也存在确定的多项式时间解。这个过程是可以证明的、并且已经被证明。
- NP困难问题（NP-hard problems）
是指这样的一类问题，它们本身的复杂度是多少无所谓（但由后面的论述可知至少是NP），但是只要这个问题找到确定的多项式时间的解，那么我们可以证明出所有的NP问题都一定存在确定的多项式时间的解。（简单叙述一下就是，只要有一个NP困难问题找到P解，那么所有NP问题都是P问题）
- NP完全问题（NP-complete problems）
如果一个问题既是NP困难问题又是NP问题，我们称之为NP完全问题。
例子
比如说，我们不知道81,785,036,517是否为素数，但是要确定277,877是否为81,785,036,517因数，我们可以直接拿去除。针对277,877来验证8,178,503,651是否为质数的动作可在多项式时间内完成，故针对某可能解来验证某数是否为质数的问题是一个P问题。
再取一个例子，假如一件问题要处理的时间非常大，不是多项式时间内可以完成的，但是他可以透过无限的计算器去算，最终计算时间复杂度只有O(n^k)，那么它就是NP（非确定性多项式时间）问题。
所谓的非确定性是指，用极大的数量去解决来达成多项式时间解决的问题。还有一个典型的例子，就是输出n个元素的全排列。即使是非确定机，也不能在多项式时间内解决，这是一个NP-hard问题。
【描述来源：wikipedia，URL：https://zh.wikipedia.org/wiki/NP_(%E8%A4%87%E9%9B%9C%E5%BA%A6)】
发展历史
描述
1955年，数学家约翰·纳什给美国国家安全局写了一封信，他推测，破解一个足够复杂的代码需要时间指数在密钥的长度上。如果证明(纳什当时是有些许怀疑的），这将意味着我们今天称之为P≠NP,因为提出了多项式时间的关键很容易验证。另一提到这个潜在的问题，是在1956年的一封由库尔特·哥德尔写给约翰·冯·诺依曼的信中。诺伊曼。哥德尔问，定理证明(现在都知道的np -complete)是否可以在二次或线性时间内得到解决，Hartmanis, Juris指出其中最重要的结果之一——如果是这样的话，那么数学证明的发现可能是自动化的。
1971年，斯蒂芬·库克（Stephen A. Cook）在1971 ACM SIGACT Symposium on the Theory of Computing,发表了The Complexity of Theorem Proving Procedures（定理证明过程的复杂性）。把以多项式时间解决为衡量标准的问题归成三大类，即NP(nondeterministic poly-nomial)，NP-complete(NP-complete)与NPhard问题. cook将polynomial-time reduction多项式时间减少(a.k.a, Cook reduction)和np完全性的概念形式化，并证明了一个np完全问题的存在，证明了Boolean satisfiability problem布尔可满足性问题(通常称为SAT),就是是np完全问题。
Leonid Levin和Stephen Cook各自发现了NP-complete问题得衍生，因为Leonid Levin对NP-complete问题进行了证明，所以NP-completeness theorem理论也被称为Cook–Levin theorem，这个也是7大千禧难题之首，Clay Mathematics Institute机构对每个问题的答案都提供了100万美元的奖励。该定理是计算机科学的一个突破，也是计算复杂性理论发展的重要一步。因为Levin发现了np完备性和平均情况复杂性。在2012年被授予Knuth奖。
Cook在1975年发表的"Feasibly Constructive Proofs and the Propositional Calculus"，他引入了等价理论PV((polynomial-time Verifiable) )，用多项式时间概念将形式化证明。在1979年的论文中对该领域做出了另一项重大贡献，与他的学生Robert A. Reckhow合作，“Efficiency of Propositional Proof Systems命题证明系统的相对效率”,在这一过程中，他们将p-仿真和有效的命题证明系统的概念形式化，从而开始了一个叫做命题证明复杂性的领域，proof complexity.他们证实了一个证明系统的存在，其中每个真公式都有一个简短的证明，相当于NP = coNP。库克与他的学生Phuong The Nguyen合著了一本名为《证明复杂性的逻辑基础》"Logical Foundations of Proof Complexity"的书。1976年，Sahni and Gonzalez提出了P完全问题的近似算法。1992年，V Kann提出了论文讨论关于np完全优化问题的逼近性.
1982,因为Cook对complexity theory.复杂性理论的贡献，因此获得图灵奖。
然而，还是莫斯科学生的列昂尼德•莱文(Leonid Levin)证明了这一点。尽管他的研究结果直到1973年才公布。在这些年来，Levin的成就的同时和独立的本质已经到来。以及过去被称为“库克定理”的是现在，通常被称为“Cook’s Theorem”。
1974年，Sahni and Gonzalez提出了P完全问题的近似算法。1992年，V Kann提出了论文讨论关于np完全优化问题的逼近性.
主要事件
年份 | 事件 | 相关论文 |
1971 | Cook, S. A.首次形式化NP问题 | Cook, S. A. (1971, May). The complexity of theorem-proving procedures. In Proceedings of the third annual ACM symposium on Theory of computing (pp. 151-158). ACM. |
1975 | Ladner, R. E.对多项式问题的时间进行讨论 | Ladner, R. E. (1975). On the structure of polynomial time reducibility. Journal of the ACM (JACM), 22(1), 155-171. |
1976 | Sahni and Gonzalez提出了P完全问题的近似算法 | Sahni, S., & Gonzalez, T. (1976). P-complete approximation problems. Journal of the ACM (JACM), 23(3), 555-565. |
1992 | Kann, V.讨论关于NP问题的逼近 | Kann, V. (1992). On the approximability of NP-complete optimization problems (Doctoral dissertation, Royal Institute of Technology). |
发展分析
瓶颈
在NP中仍然存在着大量的问题，这些问题似乎都需要超多项式时间。这些问题是否在多项式时间内无法确定，是计算机科学中最大的开放性问题之一(见P与NP (P=NP)问题)。
未来发展方向
np问题的核心就是为np是否等于p。这无论是数学家，还是其他各界人士都在努力解决的问题。这方面的一个重要概念是NP完全决策问题集，它是NP的子集，可能被非正式地描述为NP中的“最困难”问题。如果有一个多项式时间算法，那么就有一个多项式时间算法来解决NP问题。正因为如此，由于专门的研究没有找到任何np完全问题的多项式算法，一旦一个问题被证明是np完全问题，这就被广泛认为是一个关于这个问题的多项式算法不太可能存在。
Contributor: Ruiying Cai