NP (复杂度)

非决定性多项式集合（英语：non-deterministic polynomial，缩写：NP）是计算理论中最重要的集合之一，它包含P和NP-complete。

P问题是指在多项式时间内，可以找出解的决定性问题(decision problem)，而NP问题则包含可在多项式时间内验证其解是否正确，但不保证能在多项式时间内能找出解的决定性问题。NP包含P和NP-complete问题, 因此NP集合中有简单的问题和不容易快速得到解的难题。

“NP是否等于P”是计算机科学中知名的难题。

定义与推论

决定性问题

一个决定性问题(decision problem)是指其输出，只有“是”或“否”的问题。例如，搜索问题为询问 x 是否出现在一个集合 A 中?若有则输出“是”，否则输出“否”。

P问题

当一个决定性问题存在一个能在多项式时间内找出解的算法时，则称此问题落在P 的集合中。

有一些决定性问题，人类目前尚无法将他们归入集合 P 中。为了思考这些问题，于是在一般算法可采用的功能上，扩增以下虚构的新指令。这些新指令虽然不存在于现实中，但是对探讨这些难题的性质及彼此的关系，有很大的帮助。以下是这些虚构的新指令：

1. choice(S)：自集合 S 中，选出会导致正确解的一个元素。当集合 S 中无此元素时，则可任意选择一个元素。

2. failure()：代表失败结束。

3. success()：代表成功结束。
其中 choice(S)可以解释成，在求解的过程中，神奇地猜中集合 S 中其中一个元素，使其结果是成功的；并且这三个指令只需要 O(1)时间来执行。当然，choice(S) 是如何快速猜中的，在此是不需讨论的，因为毕竟它只是虚构的。在添加这些虚构功能后，所设计出的算法，被称为非决定性算法(non-deterministic algorithm)；相较之下，原来一般的算法，就称为决定性算法(deterministic algorithm)。利用非决定性算法，我们定义出另一个集合 NP。

NP问题

当一个决定性问题的解能在多项式时间内被验证时，则称此问题落在NP 的集合中。

满足问题 (satisfiability problem，简称 SAT)，就是一个NP中的典型问题。

满足问题(SAT)

令 x ₁，x ₂，…，x _n 代表布尔变量(boolean variables)(其值非真(true)即假(false)的变量)。令-x_i 代表 x_i 的相反数(negation)。一个布尔公式是将一些布尔变量及其相反数利用而且(and)和或(or)所组成的表达式。满足问题是判断是否存在一种指定每个布尔变量真假值的方式，使得一个布尔公式为真。

输入:一个 n 个变量的布尔公式

例如: (-x ₁∨ -x ₂ ∨ x ₃)∧ (x ₁ ∨ x ₄)∧(x ₂ ∨ -x ₁) 其∨代表(or)，∧代表(and)。输出:是否存在一种指定每个布尔变量真假值的方式，使得此公式为真？例如: 是(当 x ₁=真，x ₂=真，x ₃=真，x ₄=真时，此公式为真)

利用满足问题可以定义出NP-hard和NP-complete。但是我们需要一个问题转换的概念。问题转换技巧，其所需要转换的时间皆需在多项式时间(即 O (n^k))内完成。利用此多项式时间的转换，我们可以将 NP中的难题建立起一些有趣的关系。

问题转换:针对两个问题 A 和 B ，如果存在一个 O (n^k)时间的(决定性)算法，将每一个问题 A 的输入转换成问题 B 的输入，使得问题 A 有解时，当且仅当，问题 B 有解。此关系被称为，问题 A 转换成(reduce to)问题 B ，可表示成 A ∝ B 。

一个问题 L 被称为是 NP-hard，当且仅当，满足问题转换成 L(即满足问题∝L)。满足问题是 NP 中的难题，而 NP-hard 的问题则是满足问题派生(转换)出来的。

一个问题 L 被称为是 NP-complete，当且仅当，L ∈NP 而且 L ∈NP-hard。

史蒂芬库克(Stephen Cook)证明了一个十分重要的性质：

性质(A)：“任一个 NP 内的问题都可以，在多项式时间内，被转换成满足问题。”

性质(B)：“任一个 NP 内的问题都可以，在多项式时间内，被转换成任一个 NP-complete 问题。”

性质(C)：“任一个 NP 内的问题都可以，在多项式时间内，被转换成任一个 NP-hard 问题。”

性质(D)：“满足问题在集合 P 中，当且仅当，P=NP。”

例子

比如说，一个决策性问题:输入一个整数x, 请回答x是否为偶数(even number)。我们利用一个程序判断x除以2是否整除即可得到最后结果。此程序是决定性算法, 并且其时间复杂度为O(1)=O(n⁰), 因此此问题落入P集合中。

再举一个例子，下面是满足问题的一个非决定性算法。

Algorithm satisfiability (E (x ₁, … , x_n ))

{ Step 1: for i =1 to n do

x_i ←choice (true, false) /*利用 choice 直接猜中 x_i 的真假值*/

Step 2: if E (x ₁, … , x _n) is true then success () /*计算此布尔公式是否为真*/

　　　 else failure ();
}

上述的非决定性算法的时间复杂度为O(n¹)即代表满足问题落入NP集合中。

参见

NP完全问题

参考文献

引用

^ R. E. Ladner "On the structure of polynomial time reducibility," J.ACM, 22, pp. 151–171, 1975. Corollary 1.1. ACM site （页面存档备份，存于互联网档案馆）.

来源

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 34.2: Polynomial-time verification, pp. 979–983.
Michael Sipser. Sections 7.3–7.5 (The Class NP, NP-completeness, Additional NP-complete Problems). Introduction to the Theory of Computation. PWS Publishing. 1997: pp. 241–271. ISBN 0-534-94728-X.
David Harel, Yishai Feldman. Algorithmics: The Spirit of Computing, Addison-Wesley, Reading, MA, 3rd edition, 2004.

俞征武, 发现算法, 旗标出版股份有限公司, 2017.

外部链接

Complexity Zoo: NP^{[失效链接]}
Graph of NP-complete Problems^{[失效链接]}
American Scientist primer on traditional and recent complexity theory research: "Accidental Algorithms"（页面存档备份，存于互联网档案馆）

[1] R. E. Ladner "On the structure of polynomial time reducibility," J.ACM, 22, pp. 151–171, 1975. Corollary 1.1. ACM site （页面存档备份，存于互联网档案馆）.

[1]