*** Welcome to piglix ***

Polynomial time hierarchy


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.

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

where P is the set of decision problems solvable in polynomial time. Then for i ≥ 0 define

where is some standard encoding of the pair of binary strings x and w as a single binary string. L represents a set of ordered pairs of strings, where the first string x is a member of , and the second string w is a "short" () witness testifying that x is a member of . In other words, if and only if there exists a short witness w such that . Similarly, define


...
Wikipedia

...