PH (复杂度)

算法複雜度等級; 多項式層次結構中所有復雜度類的並集; 可通過二階邏輯表達的語言集

计算复杂度理论内,复杂度类PH代表所有在多项式谱系里面的复杂度类联集,亦即:

PH最早是由Larry Stockmeyer定义,是一个受限交替式图灵机(bounded alternating Turing machine)其谱系(hierarchy)的特例。这个复杂度包含于PPP(包含问题可以由多项式时间图灵机,并且能取用PP 神谕的机器所解决的复杂度类。), P#P (根据Toda's theorem),以及PSPACE里面。

PH有一个简单的逻辑描述方法:PH是一个能以二阶逻辑所表示语言的集合。

PH包含了几乎所有在PSPACE里面有名的复杂度类;举例来说,像是P, NP,和co-NP。甚至还包含了一些概率复杂度类像是BPPRP。然而,有一些证据指出BQP(以量子电脑可以在多项式时间之内解决的问题)并不包含在PH里面(Aaronson 2010).

P = NP若且唯若P = PH。这可能是一个比较简单证明PNP的方式,因为我们只要把P从比较广义的 PH分别出来即可。

参考资料