Neha Patil (Editor)

Polynomial hierarchy

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines. It is a resource-bounded counterpart to the arithmetical hierarchy and analytical hierarchy from mathematical logic.

Contents

Definitions

There are multiple equivalent definitions of the classes of the polynomial hierarchy.

Relations between classes in the polynomial hierarchy

The definitions imply the relations:

Σ i P ⊆ Δ i + 1 P ⊆ Σ i + 1 P Π i P ⊆ Δ i + 1 P ⊆ Π i + 1 P Σ i P = c o Π i P

Unlike the arithmetic and analytic hierarchies, whose inclusions are known to be proper, it is an open question whether any of these inclusions are proper, though it is widely believed that they all are. If any Σ k P = Σ k + 1 P , or if any Σ k P = Π k P , then the hierarchy collapses to level k: for all i > k , Σ i P = Σ k P . In particular, if P = NP, then the hierarchy collapses completely.

The union of all classes in the polynomial hierarchy is the complexity class PH.

Properties

The polynomial hierarchy is an analogue (at much lower complexity) of the exponential hierarchy and arithmetical hierarchy.

It is known that PH is contained within PSPACE, but it is not known whether the two classes are equal. One useful reformulation of this problem is that PH = PSPACE if and only if second-order logic over finite structures gains no additional power from the addition of a transitive closure operator.

If the polynomial hierarchy has any complete problems, then it has only finitely many distinct levels. Since there are PSPACE-complete problems, we know that if PSPACE = PH, then the polynomial hierarchy must collapse, since a PSPACE-complete problem would be a Σ k P -complete problem for some k.

Each class in the polynomial hierarchy contains ≤ m P -complete problems (problems complete under polynomial-time many-one reductions). Furthermore, each class in the polynomial hierarchy is closed under ≤ m P -reductions: meaning that for a class C in the hierarchy and a language L ∈ C , if A ≤ m P L , then A ∈ C as well. These two facts together imply that if K i is a complete problem for Σ i P , then Σ i + 1 P = N P K i , and Π i + 1 P = c o N P K i . For instance, Σ 2 P = N P S A T . In other words, if a language is defined based on some oracle in C , then we can assume that it is defined based on a complete problem for C . Complete problems therefore act as "representatives" of the class for which they are complete.

The Sipser–Lautemann theorem states that the class BPP is contained in the second level of the polynomial hierarchy.

Kannan's theorem states that for any k, Σ 2 is not contained in SIZE(nk).

Toda's theorem states that the polynomial hierarchy is contained in P#P.

References

Polynomial hierarchy Wikipedia
(Text) CC BY-SA