Quantifier and oracle characterizations of ph

For $k\ge 1$, transcript normal form gives $N{P}^{{\mathrm{\Sigma }}_k^p}\subseteq {\mathrm{\Sigma }}_{k+1}^p$. Conversely, guess the first block of a ${\mathrm{\Sigma }}_{k+1}^p$ predicate. The remaining language of pairs is in ${\mathrm{\Pi }}_k^p$; query its complementary ${\mathrm{\Sigma }}_k^p$ language and flip the answer. The two procedures give both inclusions. For $k=0$, polynomial-time oracle calls can be simulated directly in polynomial time, and the first-level verifier identity gives the result.

Every language at positive level reduces to the fixed complete QBF language; replace each adaptive query by its reduction. Query lengths and query counts remain polynomial. Negating the oracle machine's acceptance convention gives the complementary nondeterministic class; the displayed Delta equality is its definition. The first-level complete QBF language is simply formula satisfiability with its assignment block made explicit.

For an alternating machine, replace each existential or universal choice block by a polynomial-length string of its branch choices, ignoring unused bits. Deterministic steps between changes of polarity are simulated by the final predicate. Conversely, realize each quantified string by successive binary choices of the required polarity and then evaluate the predicate. Acceptance at an existential node means some child accepts, and at a universal node every child accepts; recursive evaluation of the finite tree proves the equivalence. Halted branches can be padded with ignored choices.

The first inclusion and the guess-and-complement-query construction work identically with a fixed base $A$, using the relative part of transcript normal form. Both the outer machine and its predicate retain access to that same $A$; this is the claimed relative oracle characterization. It does not assert unrelativized formula completeness for arbitrary $A$.