Editing Polynomial hierarchy (section)

===Oracle definition===
For the oracle definition of the polynomial hierarchy, define

:<math>\Delta_0^\mathrm{P} := \Sigma_0^\mathrm{P} := \Pi_0^\mathrm{P} := \mathrm{P},</math>

where [[P (complexity)|P]] is the set of [[decision problem]]s solvable in [[polynomial time]]. Then for i ≥ 0 define

:<math>\Delta_{i+1}^\mathrm{P} := \mathrm{P}^{\Sigma_i^\mathrm{P}}</math>
:<math>\Sigma_{i+1}^\mathrm{P} := \mathrm{NP}^{\Sigma_i^\mathrm{P}}</math>
:<math>\Pi_{i+1}^\mathrm{P} := \mathrm{coNP}^{\Sigma_i^\mathrm{P}}</math>

where <math>\mathrm{P}^{\rm A}</math> is the set of [[decision problem]]s solvable in polynomial time by a [[Turing machine]] augmented by an [[oracle machine|oracle]] for some complete problem in class A; the classes <math>\mathrm{NP}^{\rm A}</math> and <math>\mathrm{coNP}^{\rm A}</math> are defined analogously.  For example, <math> \Sigma_1^\mathrm{P} = \mathrm{NP}, \Pi_1^\mathrm{P} = \mathrm{coNP} </math>, and <math> \Delta_2^\mathrm{P} = \mathrm{P^{NP}} </math> is the class of problems solvable in polynomial time by a deterministic Turing machine with an oracle for some NP-complete problem.<ref>Completeness in the Polynomial-Time Hierarchy A Compendium, M. Schaefer, C. Umans</ref>