Polynomial time hierarchy

The polynomial time hierarchy ( PH , also: polynomial hierarchy) is the assumed structure of complexity classes between NP and PSPACE . The basic idea behind the polynomial time hierarchy is the question of whether the performance of a Turing machine can be increased by adding oracles .

definition

Pictorial representation of the polynomial time hierarchy. The arrows indicate inclusion.

The polynomial time hierarchy consists of the families , and of complexity classes. The classes , and form the -th level of the hierarchy. For level 0 it applies that all three classes are identical to class P , the problems solvable in polynomial time, i.e. H. . Level 1 applies that , and . The complexity classes in the polynomial time hierarchy can be defined in several equivalent ways. ${\displaystyle (\Delta _{i})_{i\geq 1}}$ ${\displaystyle (\Sigma _{i})_{i\geq 1}}$ ${\displaystyle (\Pi _{i})_{i\geq 1}}$ ${\displaystyle \Delta _{i}}$ ${\displaystyle \Sigma _{i}}$ ${\displaystyle \Pi _{i}}$ ${\displaystyle i}$ ${\displaystyle \Delta _{0}^{\rm {P}}=\Sigma _{0}^{\rm {P}}=\Pi _{0}^{\rm {P}}={\mbox{P}},}$ ${\displaystyle \Delta _{1}^{\rm {P}}={\mbox{P}}}$ ${\displaystyle \Sigma _{1}^{\rm {P}}={\mbox{NP}}}$ ${\displaystyle \Pi _{1}^{\rm {P}}={\mbox{coNP}}}$

Definition with oracle-Turing machines

An oracle Turing machine is an extension of a Turing machine. A Turing machine with oracle (where a language is) can decide whether a word with a single calculation step to hear or not. ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle w}$ ${\displaystyle A}$

Such a construction is symbolically represented as follows:

• ${\displaystyle B^{A}}$means that a Turing machine consults with an oracle . ${\displaystyle M}$ ${\displaystyle L(M)=B}$ ${\displaystyle A}$

With regard to complexity classes, the following notation results:

• ${\displaystyle {\mbox{P}}^{\mbox{NP}}}$ (read: P to the power of NP) is the set of all problems that can be solved by a Turing machine that only consumes polynomial times depending on the input length, but can use an oracle for the solution that is able to solve a problem from NP to decide.

The complexity classes of the polynomial time hierarchy are defined as follows:

The following applies to level 0:

${\displaystyle \Delta _{0}^{\rm {P}}:=\Sigma _{0}^{\rm {P}}:=\Pi _{0}^{\rm {P}}:={\mbox{P}},}$

The other classes of the hierarchy are inductively defined. For this purpose, Oracle Turing machines that use a complexity class of the previous level of the hierarchy as oracles are used:

${\displaystyle \Delta _{i+1}^{\rm {P}}:={\mbox{P}}^{\Sigma _{i}^{\rm {P}}}}$

${\displaystyle \Sigma _{i+1}^{\rm {P}}:={\mbox{NP}}^{\Pi _{i}^{\rm {P}}}}$

${\displaystyle \Pi _{i+1}^{\rm {P}}:={\mbox{coNP}}^{\Sigma _{i}^{\rm {P}}}}$

It is especially true , and . ${\displaystyle \Sigma _{1}^{\rm {P}}={\mbox{NP}}}$ ${\displaystyle \Pi _{1}^{\rm {P}}={\mbox{coNP}}}$ ${\displaystyle \Delta _{2}^{\rm {P}}={\mbox{P}}^{\mbox{NP}}}$

The alternative definition is often found in the literature . Since every oracle can be converted into an oracle by negating the output (and vice versa), this definition is equivalent to the one chosen above. ${\displaystyle \Sigma _{i}^{\rm {P}}}$ ${\displaystyle \Sigma _{i+1}^{\rm {P}}:={\mbox{NP}}^{\Sigma _{i}^{\rm {P}}}}$ ${\displaystyle \Sigma _{i}^{\rm {P}}}$ ${\displaystyle \Pi _{i}^{\rm {P}}}$

Definition with alternating Turing machines

Alternating Turing machines are an extension of non-deterministic Turing machines in which the states of the machine are differentiated into existential and universal states. A calculation based on an existential state accepts the input if at least one of the possible calculations is accepted and a calculation based on a universal state only accepts if all possible calculations are accepted.

The polynomial time hierarchy can be defined using alternating Turing machines as follows.

• The class contains the languages ​​that can be decided by an alternating Turing machine in polynomial time, so that the initial state is existential and on every possible calculation path there is only one change between the two quantifications of the states. ${\displaystyle \Sigma _{i}^{\rm {P}}}$ ${\displaystyle i-1}$

• The class contains the languages ​​that can be decided by an alternating Turing machine in polynomial time, so that the initial state is universal and on each possible calculation path there is only one change between the two quantifications of the states. ${\displaystyle \Pi _{i}^{\rm {P}}}$ ${\displaystyle i-1}$

Definition with alternating quantifiers and relations

This definition uses a multi-digit relation via bit vectors , which can be decided in polynomial time, and alternating quantification via these bit vectors. Another alternation of quantifiers is added for each level of the hierarchy. The formal definition of the complexity classes is as follows.

A language is in the complexity class if it has ${\displaystyle L}$ ${\displaystyle \Sigma _{i}^{\rm {P}}}$

• a Turing machine that works in polynomial time and ${\displaystyle M}$
• of a polynomial ${\displaystyle q}$

can be characterized as follows

${\displaystyle x\in L\Leftrightarrow \exists u_{1}\in \{0,1\}^{q(|x|)}\,\forall u_{2}\in \{0,1\}^{q(|x|)}\dots Q_{i}u_{i}\in \{0,1\}^{q(|x|)}M(x,u_{1},\dots ,u_{i})=1}$

where is an universal quantifier for even indices and an existential quantifier for odd indices . ${\displaystyle Q_{i}}$ ${\displaystyle \forall }$ ${\displaystyle \exists }$

The class consists of the languages ​​whose complement language is in, i.e. H. . ${\displaystyle \Pi _{i}^{\rm {P}}}$ ${\displaystyle \Sigma _{i}^{\rm {P}}}$ ${\displaystyle \Pi _{i}^{\rm {P}}={\mbox{co}}\Sigma _{i}^{\rm {P}}}$

properties

The union of all classes of the polynomial time hierarchy PH forms a subset of PSPACE:

• ${\displaystyle {\mbox{PH}}:=\bigcup _{i=0}^{\infty }\Delta _{i}^{\rm {P}}=\bigcup _{i=0}^{\infty }\Sigma _{i}^{\rm {P}}=\bigcup _{i=0}^{\infty }\Pi _{i}^{\rm {P}}\subseteq {\mbox{PSPACE}}}$

It is generally assumed that this inclusion is real and that the polynomial hierarchy has infinitely many different levels, i.e. that is , that applies. But if in reality , PSPACE-complete problems like TQBF are already in one and the polynomial hierarchy collapses, i.e. H. there is one with: ${\displaystyle \forall i\geq n:\Sigma _{i}^{\rm {P}}\neq \Sigma _{i+1}^{\rm {P}}}$ ${\displaystyle {\mbox{PH}}={\mbox{PSPACE}}}$ ${\displaystyle \Sigma _{n}^{\rm {P}}}$ ${\displaystyle n}$

${\displaystyle \forall i\geq n:\Delta _{i}^{\rm {P}}=\Delta _{n}^{\rm {P}}}$(Analog also for and ) ${\displaystyle \Sigma _{i}}$ ${\displaystyle \Pi _{i}}$

If P and NP are equal , the polynomial time hierarchy collapses completely, i.e. H. all and would be the same P. In general: ${\displaystyle \Sigma _{n}^{\rm {P}}}$ ${\displaystyle \Pi _{n}^{\rm {P}}}$

• If for one :, then for all : ${\displaystyle k\geq 0}$ ${\displaystyle \Sigma _{k}^{\rm {P}}=\Sigma _{k+1}^{\rm {P}}}$ ${\displaystyle i>k}$ ${\displaystyle \Sigma _{k}^{\rm {P}}=\Sigma _{i}^{\rm {P}}}$

In descriptive complexity theory , the second level predicate logic describes the polynomial time hierarchy.

literature

• Michael Sipser: Introduction to the Theory of Computation . 3. Edition. ISBN 0-534-94728-X , 10.3 Alternation - The polynomial time hierarchy, p. 414 .
• Sanjeev Arora , Boaz Barak: Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge; New York, ISBN 978-0-521-42426-4 , 5. The polynomial hierarchy and alternations ( Draft [PDF]).
• Christos H. Papadimitriou : Computational Complexity . Addison-Wesley, Reading / Mass, ISBN 978-0-201-53082-7 , 17.2 The Polynomial Hierarchy.
• Marcus Schaefer, Christopher Umans: Completeness in the Polynomial-Time Hierarchy: A Compendium . In: ACM SIGACT News . tape 33 , no. 3 , September 2002, ISSN  0163-5700 , p. 32-49 , doi : 10.1145 / 582475.582484 .
• Marcus Schaefer, Christopher Umans: Completeness in the Polynomial-Time Hierarchy: Part II . In: ACM SIGACT News . tape 33 , no. 4 , December 2002, ISSN  0163-5700 , p. 22-36 , doi : 10.1145 / 601819.601829 .

Web links

• PH . In: Complexity Zoo. (English)

Individual evidence

1. ↑ Evgeny Dantsin, Thomas maker, Georg Gottlob, Andrei Voronkov: Complexity and Expressive Power of Logic Programming . In: ACM Comput. Surv. tape 33 , no. 3 , September 1, 2001, ISSN  0360-0300 , p. 374-425 , doi : 10.1145 / 502807.502810 .