Editing Polynomial hierarchy (section)

==Relations between classes in the polynomial hierarchy==
[[Image:Polynomial time hierarchy.svg|250px|thumb|right|Commutative diagram equivalent to the polynomial time hierarchy. The arrows denote inclusion.]]
The union of all classes in the polynomial hierarchy is the complexity class '''PH'''.

The definitions imply the relations:

:<math>\Sigma_i^\mathrm{P} \subseteq \Delta_{i+1}^\mathrm{P} \subseteq \Sigma_{i+1}^\mathrm{P}</math>
:<math>\Pi_i^\mathrm{P} \subseteq \Delta_{i+1}^\mathrm{P} \subseteq \Pi_{i+1}^\mathrm{P}</math>
:<math>\Sigma_i^\mathrm{P} = \mathrm{co}\Pi_{i}^\mathrm{P}</math>

Unlike the arithmetic and analytic hierarchies, whose inclusions are known to be proper, it is an open question whether any of these inclusions are proper, though it is widely believed that they all are.  If any <math>\Sigma_k^\mathrm{P} = \Sigma_{k+1}^\mathrm{P}</math>, or if any <math>\Sigma_k^\mathrm{P} = \Pi_{k}^\mathrm{P}</math>, then the hierarchy ''collapses to level k'': for all <math>i > k</math>, <math>\Sigma_i^\mathrm{P} = \Sigma_k^\mathrm{P}</math>.<ref>Arora and Barak, 2009, Theorem 5.4</ref> In particular, we have the following implications involving unsolved problems:

* [[P versus NP problem|'''P''' = '''NP''']] if and only if '''P''' = '''PH'''.<ref>{{cite book|title=Handbook of Discrete and Combinatorial Mathematics|series=Discrete Mathematics and Its Applications|editor-first=Kenneth H.|editor-last=Rosen|edition=2nd|publisher=CRC Press|year=2018|pages=1308–1314|isbn=9781351644051|chapter=17.5 Complexity classes|first=Lane|last=Hemaspaandra}}</ref>
* If '''NP''' = '''[[co-NP]]''' then '''NP''' = '''PH'''. ('''co-NP''' is <math>\Pi_1^\mathrm{P}</math>.)
The case in which '''NP''' = '''PH''' is also termed as a ''collapse'' of the '''PH''' to ''the second level''. The case '''P''' = '''NP''' corresponds to a collapse of '''PH''' to '''P'''.

{{Unsolved|computer science|{{tmath|1= \mathrm{P} \overset{?}{=} \mathrm{NP} }}}}

The question of collapse to the first level is generally thought to be extremely difficult. Most researchers do not believe in a collapse, even to the second level.