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