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 ${\displaystyle \langle x,w\rangle \in \{0,1\}^{*}}$ 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 ${\displaystyle \exists ^{p}L}$, and the second string w is a "short" (${\displaystyle |w|\leq p(|x|)}$) witness testifying that x is a member of ${\displaystyle \exists ^{p}L}$. In other words, ${\displaystyle x\in \exists ^{p}L}$ if and only if there exists a short witness w such that ${\displaystyle \langle x,w\rangle \in L}$. Similarly, define

...
Wikipedia