Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Polynomial hierarchy
Summary
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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.