P-完全

在计算复杂度理论内，标示了P-完全的决定型问题对于分析

1. 哪些问题很难有效的平行处理，
2. 哪些问题很难在有限空间内解决掉。

相当的有用。

更正式的说，一个决定型问题是P-完全(一个P里面的完全问题)：若这问题本身在P里面，且所有在P内的问题，都可以化约为此问题。

特定的化约方式会产生使用差异而且会影响问题集合的大小。 若我们使用NC的化约，亦即，可以在多项式对数时间内，以平行运作的电脑在多项式个数之内的处理器下完成的化约，基于一个未被证明的假设 NC ≠ P，则我们可知所有的P-完全问题在NC之外，因此无法被有效率的平行处理化。如果我们使用比较弱的 log-space 化约，前面的说法维持为真，但是多了一个P-完全问题会在L之外的推论， 基于另一个较弱的，尚未被证明的假设L ≠ P。这里需要注意到根据后者定义出的P-完全 会是一个比前者小一点的集合。

动机

找到一个有效率平行处理P-完全问题的方法会导出NC = P的结论(另一个虽没有证明，但是一般认为是否的假说)。

另外，我们也可以将之视为"需要超过对数空间的问题"；因为，一个针对P-完全问题提出使用对数空间解决的算法 (using the definition based on log-space reductions) 将会推导出L = P(另一个虽没有证明，但是一般认为是否的假说)。

P-完全问题

最基本的P-完全问题是：给定一个图灵机，此机器的输入，以及一个数字T (以一进制表示)，这个给定的图灵机是否会在 T 步骤之内结束运算？？这个问题是P-完全证明如下：

首先，这个问题包含于P之内，因为我们可以让图灵机实际模拟跑完前面T个步骤来得到结论。这只会耗费多项式的时间。

又，如果我们可以平行化这个问题，那就代表我们必须要允许一个图灵机能平行处理任何问题。而若这个问题在NC之内，那所有包含在P的问题都将也可以化约为此问题，故得证。

若这个数字是以二进制系统表示，则这个问题会变成EXPTIME-完全.

这个问题展示了一个在研究P-完全问题的理论常用的技巧。我们并不关注在这问题是否可以快速的用平行机器处理，我们关注的地方在于这个问题是否在使用平行机器时会变的比起使用非平行的机器快速"很多"。因此，我们要先将问题改写为P的版本。这就是为何我们需要将T以一进位表示。若数字T是使用二进制表示 (一个包含n个零与一的字串，n = log T)，那么用最直观的算法运作的时间就会变成2ⁿ. 但是，若T是用一进位系统表示 (一个包含T个一的字串)，则花费的时间就变成只有n(因为跑的时间不变，但是输入资料变大了，因此时间复杂度下降)。 借着以一进位而非二进制来表示T， we have reduced the obvious sequential algorithm 从对数时间转换到到线性时间。 因此将这个问题使用序列解法的时间限制在P之内。 Then, it will be in NC 当且仅当这问题是可以平行化处理的。

许多其他的问题也已被证明属于P-完全，因此广泛的被认为是自然属于序列化(也就是，不容易平行化)的。 这些包含了以下的问题(无论是否是以决定型问题的方式表示，时间上都一样为P-完全):

要证明一个给定的问题是P-完全，一个常见的作法是将一个已知是P-完全的问题化约为这个给定的问题。

在1999年，Jin-Yi Cai 和 D. Sivakumar，基于Ogihara的理论，推导出若存在一个稀疏语言属于P-完全，则L = P。

未知是否为P-完全的问题

有一些问题尚不清楚是属于NP-难或者是P。这一些问题(例如说，整数分解)被怀疑是比较困难的。 类似的有些问题尚不清楚是属于P-完全或者NC，但是一般被认为是不容易平行化的。这类问题的范例有找出两给定整数最大公因数的决定型问题版本，和给出对扩展欧几里得算法出入两个整数之后的答案。

参考文献

来源

• Greenlaw, Raymond, James Hoover, and Walter Ruzzo. 1995. Limits To Parallel computation; P-完全ness Theory. ISBN 0-19-508591-4. — Develops the theory, then catalogs 96 P-完全 problems.
• Satoru Miyano, Shuji Shiraishi, and Takayoshi Shoudai. A List of P-完全 Problems. Kyushu University, RIFIS-TR-CS-17. December 1990.