P-完全

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

另外，我们也可以将之视为"需要超过对数空间的问题"；因为，一个针对P-完全问题提出使用对数空间解决的算法 (using the definition based on log-space reductions) 将会推导出L = 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。^[1]

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

引用

来源