Ph adaptive oracle transcript normal form

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 each fixed $k\ge 0$, both ${\mathrm{\Sigma }}_k^p$ and ${\mathrm{\Pi }}_k^p$ are closed under polynomial-time many-one preimages and polynomially many uniformly indexed conjunctions and disjunctions. Precisely, if the language of pairs $(x,i)$ lies in the class and $0\le i<q(\mathrm{\mid }x\mathrm{\mid })$ for a polynomial-time computable polynomial bound $q$, then both “every such $i$” and “some such $i$” define languages in that class. Complements interchange ${\mathrm{\Sigma }}_k^p$ and ${\mathrm{\Pi }}_k^p$, and each is contained in both classes at level $k+1$. These assertions also hold with one fixed base oracle. (Ph quantifier block closure).