P (复杂度)

复杂度关系韦恩图

在计算复杂度理论中，P（polynomial time class）是在复杂度类问题中可于确定型图灵机以多项式量级（或称多项式时间）求解的决定性问题。

P通常表示那类可以“有效率地解决”或“温驯”的可计算型问题，就算指数级非常高也可以算作“温驯”，例如RP与BPP问题。当然P类别存在很多现实处理上一点也不温驯的问题，例如一些至少需要n^1000000指令来解决的问题。很多情况下存在着更难的复杂度问题

在P中令人注目的问题

P包含了很多已知的自然问题，例如决定性版本的线性规划，计算最大公因数，以及发现最大匹配。在2002年，判别一个数是否为质数也被人解出是一个P问题。与功能性问题相关的类别是FP。

与其他类别的关系

P的扩大集合是NP，此复杂度类是一个可在多项式时间以非确定型图灵机决定答案的问题的集合。因此我们可知道P是NP的子集，且虽然未证明，但大部分专家相信P是NP的严格子集（即NP一定大于且包含P集合）。

P也已知至少大于L一个可在对数量级的存储器空间上决定的问题的类别。一个判定算法使用了O(log n)的空间就不可能使用超过2^{O(log n)}=n^O(1)的时间，因为这是所有可能组合方式的总数，因此L是P的子集合。另一个重要问题是：L是否相等于P？我们已知P=AL（问题可在对数存储器上以交替式图灵机解决的问题之集合），而P也已知不大于PSPACE（可在多项式空间判定的问题）。再一次，我们面对P是否等于PSPACE的未知问题。整理一下上述问题：

${\mbox{L}}\subseteq {\mbox{AL}}={\mbox{P}}\subseteq {\mbox{NP}}\subseteq {\mbox{PSPACE}}\subseteq {\mbox{EXPTIME}}$

EXPTIME指的是可在指数时间解答的问题类别。在上列的类别关系中，只有两个严格包含关系是确定的：

• P严格包含于EXPTIME之中。因此所有EXPTIME-hard问题在P集合之外，且最少一个P右方的包含关系是严格的（事实上，大部分人认为P右边三个集合都是严格包含P）。
• L严格包含于PSPACE集合中。

在P问题中最困难的是P-完全问题。

另一个P的扩大集合是P/poly，或非统一多项式时间。若一个问题落于P\poly，则它可以在依据输入内容的长度下给予提示字符串（advice string）的情况下，以确定性多项式时间解决。然而，不像NP，此多项式时间机器不需要侦测伪造提示字符串；因为它不是一个验证机器。P/poly是一个几乎包含所有实际算法的巨大类别，包含所有BPP。如果P/poly包含了NP，则整个多项式谱系将会下降到第二层次结构。另一方面，它也包含一些不切实际的算法，包含一些可决定问题，例如一元版的任何非决定性问题。

性质

多项式时间算法拥有组装封闭性。换句话说，若我写了一个内容是多项式时间的函数（若视函数调用为固定时间），且其它被本函数调用的副函数也属于多项式时间，则整个组合起来的算法也会是多项式时间。因此P是自我低陷的，这也是P被认为是无关机器类型的主要理由：任何机器特征（例如随机存取）可以用多项式时间算法模仿的话，可在一些更简单的机器以其他多项式时间算法组合并化约而成，且时间复杂度依然是P。

历史

Kozen指出Cobham与Edmonds是最可信，最早创造多项式时间这个名词的人。

参考资料

• C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. ISBN 978-0-201-53082-7.
• Complexity Zoo: P，P/poly
• Thomas H. Cormen，Charles E. Leiserson，Ronald L. Rivest，and Clifford Stein。Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 978-0-262-03293-3. Section 34.1: Polynomial time, pp.971–979.
• Michael Sipser. Introduction to the Theory of Computation. PWS Publishing. 1997. ISBN 978-0-534-94728-6.  Section 7.2: The Class P, pp.234–241.