Relativized complexity class

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 class P and The class NP via polynomial-time verifiers.

For ${\mathrm{\Sigma }}_k^{p,A}$ and ${\mathrm{\Pi }}_k^{p,A}$, replace the deterministic predicate in Polynomial hierarchy levels 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\}$.