Editing Polynomial hierarchy (section)

==Problems==
{{unordered list
|1=
An example of a natural problem in <math>\Sigma_2^\mathrm{P}</math> is ''[[circuit minimization]]'': given a number ''k'' and a circuit ''A'' computing a [[Boolean function]] ''f'', determine if there is a circuit with at most ''k'' gates that computes the same function ''f''. Let {{mathcal|C}} be the set of all boolean circuits. The language

:<math> L = \left\{ \langle A,k,B,x \rangle \in \mathcal{C} \times \mathbb{N} \times \mathcal{C} \times \{0,1\}^*  
\left|
B \text{ has at most } k \text{ gates, and } A(x)=B(x) 
\right.
\right\} </math>

is decidable in polynomial time. The language

:<math> \mathit{CM} = \left\{ \langle A,k \rangle \in \mathcal{C} \times \mathbb{N} 
\left| 
\begin{matrix}
\text{there exists a circuit } B \text{ with at most } k \text{ gates } \\
\text{ such that } A \text{ and } B \text{ compute the same function} 
\end{matrix}
\right.
\right\} </math>

is the circuit minimization language. <math> \mathit{CM} \in \Sigma_2^\mathrm{P} (= \exists^\mathrm{P} \forall^\mathrm{P} \mathrm{P}) </math> because {{mvar|L}} is decidable in polynomial time and because, given <math> \langle A,k \rangle </math>, <math> \langle A,k \rangle \in \mathit{CM}</math> if and only if ''there exists'' a circuit {{mvar|B}} such that ''for all'' inputs {{mvar|x}}, <math> \langle A,k,B,x \rangle \in L </math>.

|2=
A complete problem for <math>\Sigma_k^\mathrm{P}</math> is '''satisfiability for quantified Boolean formulas with ''k'' – 1 alternations of quantifiers''' (abbreviated '''QBF<sub>k</sub>''' or '''QSAT<sub>k</sub>'''). This is the version of the [[boolean satisfiability problem]] for <math>\Sigma_k^\mathrm{P}</math>. In this problem, we are given a Boolean formula ''f'' with variables partitioned into ''k'' sets ''X''<sub>1</sub>, ..., ''X<sub>k</sub>''. We have to determine if it is true that 
:<math> \exists X_1 \forall X_2 \exists X_3 \ldots f</math>
That is, is there an assignment of values to variables in ''X''<sub>1</sub> such that, for all assignments of values in ''X''<sub>2</sub>, there exists an assignment of values to variables in ''X''<sub>3</sub>, ... ''f'' is true?

The variant above is complete for <math>\Sigma_k^\mathrm{P}</math>. The variant in which the first quantifier is "for all", the second is "exists", etc., is complete for <math>\Pi_k^\mathrm{P}</math>. Each language is a subset of the problem obtained by removing the restriction of ''k'' – 1 alternations, the '''PSPACE'''-complete problem [[TQBF]].

|3=
A Garey/Johnson-style list of problems known to be complete for the second
and higher levels of the polynomial hierarchy can be found in [http://ovid.cs.depaul.edu/documents/phcom.pdf this Compendium].

}}