Standard containments relativize

Given: the objects and hypotheses in the statement above.

Fix a total language $A\subseteq \{0,1{\}}^{\ast }$. An oracle machine writes a query word and receives its membership bit in $A$ in one answer step. Query writing counts toward time and the query tape toward space. A polynomial time clock bounds every branch for every oracle. $P^A$ and $N{P}^A$ are deterministic and nondeterministic polynomial-time oracle classes, respectively; the latter equivalently uses a polynomial-length witness and a deterministic polynomial-time $A$-oracle verifier. Use the conventions of the stated convention and the stated convention. For ${\mathrm{\Sigma }}_k^{p,A}$ and ${\mathrm{\Pi }}_k^{p,A}$, replace the deterministic predicate in the stated convention by a $P^A$ predicate; level zero is $P^A$. Define ${\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}}^A$ by deterministic polynomial space under the charged-query convention. For a language class $\mathcal{D}$, $P^{\mathcal{D}}={\bigcup }_{B\in \mathcal{D}}{P}^B$ and $N{P}^{\mathcal{D}}={\bigcup }_{B\in \mathcal{D}}N{P}^B$. Finally ${\mathrm{\Delta }}_{k+1}^p=P^{{\mathrm{\Sigma }}_k^p}$. With a fixed base oracle, a machine may query both $A$ and a language $B$; encode this by the tagged union $A\oplus B=\{0x:x\in A\}\cup \{1x:x\in B\}$. (Relativized complexity class).

For every $k\ge 0$, ${\mathrm{\Sigma }}_{k+1}^p=N{P}^{{\mathrm{\Sigma }}_k^p},{\mathrm{\Pi }}_{k+1}^p=coN{P}^{{\mathrm{\Sigma }}_k^p},{\mathrm{\Delta }}_{k+1}^p=P^{{\mathrm{\Sigma }}_k^p}\mathrm{.}$ For $k\ge 1$ a fixed complete bounded-alternation QBF language can replace the class oracle. At $k=1$, this gives the usual satisfiability oracle. The quantifier levels also equal polynomial-time alternating computations with at most $k$ blocks of existential/universal choices, beginning with the indicated polarity. With a fixed base oracle $A$, the same oracle characterization holds using access to both $A$ and a language in ${\mathrm{\Sigma }}_k^{p,A}$. (Quantifier and oracle characterizations of ph).

For every $k\ge 0$, ${\mathrm{\Sigma }}_k^p\cup {\mathrm{\Pi }}_k^p\subseteq {\mathrm{\Delta }}_{k+1}^p\subseteq {\mathrm{\Sigma }}_{k+1}^p\cap {\mathrm{\Pi }}_{k+1}^p\mathrm{.}$ Moreover $\mathrm{P}\mathrm{H}\subseteq \mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$. (Ph containments and polynomial space).