Editing Polynomial hierarchy (section)

{{Short description|Computer science concept}}
{{no footnotes|date=July 2019}}

In [[computational complexity theory]], the '''polynomial hierarchy''' (sometimes called the '''polynomial-time hierarchy''') is a [[hierarchy (mathematics)|hierarchy]] of [[complexity class]]es that generalize the classes '''[[NP (complexity)|NP]]''' and '''[[co-NP]]'''.<ref>Arora and Barak, 2009, pp.97</ref> Each class in the hierarchy is contained within '''[[PSPACE]]'''. The hierarchy can be defined using [[oracle machine]]s or [[alternating Turing machine]]s. 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 reduction]]s) that ask if [[quantified Boolean formula]]e 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.