In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. The hierarchy can be defined using oracle machines or alternating Turing machines. It is a resource-bounded counterpart to the arithmetical hierarchy and analytical hierarchy from mathematical logic. The union of the classes in the hierarchy is denoted PH. Classes within the hierarchy have complete problems (with respect to polynomial-time reductions) that ask if quantified Boolean formulae hold, for formulae with restrictions on the quantifier order. It is known that equality between classes on the same level or consecutive levels in the hierarchy would imply a "collapse" of the hierarchy to that level. There are multiple equivalent definitions of the classes of the polynomial hierarchy. For the oracle definition of the polynomial hierarchy, define where P is the set of decision problems solvable in polynomial time. Then for i ≥ 0 define where is the set of decision problems solvable in polynomial time by a Turing machine augmented by an oracle for some complete problem in class A; the classes and are defined analogously. For example, , and is the class of problems solvable in polynomial time by a deterministic Turing machine with an oracle for some NP-complete problem. For the existential/universal definition of the polynomial hierarchy, let L be a language (i.e. a decision problem, a subset of {0,1}*), let p be a polynomial, and define where is some standard encoding of the pair of binary strings x and w as a single binary string. The language 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 Note that De Morgan's laws hold: and , where Lc is the complement of L.