Editing Polynomial hierarchy (section)

===Quantified Boolean formulae definition ===
For the existential/universal definition of the polynomial hierarchy, let {{mvar|L}} be a [[formal language|language]] (i.e. a [[decision problem]], a subset of {0,1}<sup>*</sup>), let {{mvar|p}} be a [[polynomial]], and define

: <math> \exists^p L := \left\{ x \in \{0,1\}^* \ \left| \ \left( \exists w \in \{0,1\}^{\leq p(|x|)} \right) \langle x,w \rangle \in L \right. \right\}, </math>

where <math>\langle x,w \rangle \in \{0,1\}^*</math> 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 <math>\exists^p L</math>, and the second string ''w'' is a "short" (<math>|w| \leq p(|x|) </math>) witness testifying that ''x'' is a member of <math>\exists^p L</math>. In other words, <math>x \in \exists^p L</math> if and only if there exists a short  witness ''w'' such that <math> \langle x,w \rangle \in L </math>. Similarly, define

: <math> \forall^p L := \left\{ x \in \{0,1\}^* \ \left| \ \left( \forall w \in \{0,1\}^{\leq p(|x|)} \right) \langle x,w \rangle \in L \right. \right\} </math>
Note that [[De Morgan's laws]] hold: <math> \left( \exists^p L \right)^{\rm c} = \forall^p L^{\rm c} </math> and <math> \left( \forall^p L \right)^{\rm c} = \exists^p L^{\rm c} </math>, where ''L''<sup>c</sup> is the complement of ''L''.

Let {{mathcal|C}} be a class of languages. Extend these operators to work on whole classes of languages by the definition

:<math>\exists^\mathrm{P} \mathcal{C} := \left\{\exists^p L \ | \ p \text{ is a polynomial and } L \in \mathcal{C} \right\}</math>
:<math>\forall^\mathrm{P} \mathcal{C} := \left\{\forall^p L \ | \ p \text{ is a polynomial and } L \in \mathcal{C} \right\}</math>

Again, De Morgan's laws hold: <math> \mathrm{co} \exists^\mathrm{P} \mathcal{C} = \forall^\mathrm{P} \mathrm{co} \mathcal{C} </math> and <math> \mathrm{co} \forall^\mathrm{P} \mathcal{C} = \exists^\mathrm{P} \mathrm{co} \mathcal{C} </math>, where <math>\mathrm{co}\mathcal{C} = \left\{ L^c | L \in \mathcal{C} \right\}</math>.

The classes '''[[NP (complexity)|NP]]''' and '''[[co-NP]]''' can be defined as <math> \mathrm{NP} = \exists^\mathrm{P} \mathrm{P} </math>, and <math> \mathrm{coNP} = \forall^\mathrm{P} \mathrm{P} </math>, where '''[[P (complexity)|P]]''' is the class of all feasibly (polynomial-time) decidable languages. The polynomial hierarchy can be defined recursively as

:<math> \Sigma_0^\mathrm{P} := \Pi_0^\mathrm{P} := \mathrm{P} </math>
:<math> \Sigma_{k+1}^\mathrm{P} := \exists^\mathrm{P} \Pi_k^\mathrm{P} </math>
:<math> \Pi_{k+1}^\mathrm{P} := \forall^\mathrm{P} \Sigma_k^\mathrm{P} </math>

Note that <math> \mathrm{NP} = \Sigma_1^\mathrm{P} </math>, and <math> \mathrm{coNP} = \Pi_1^\mathrm{P} </math>.

This definition reflects the close connection between the polynomial hierarchy and the [[arithmetical hierarchy]], where '''[[Decidable language|R]]''' and '''[[Recursively enumerable language|RE]]''' play roles analogous to '''[[P (complexity)|P]]''' and '''[[NP (complexity)|NP]]''', respectively. The [[analytic hierarchy]] is also defined in a similar way to give a hierarchy of subsets of the [[Baire space (set theory)|real number]]s.