The Polynomial Hierarchy and Relativization

The bounded-block definition supplies one uniform predicate for $(x,i)$, not a separately chosen machine for each index. A polynomial-time preimage first computes its image; witness lengths can be padded to a polynomial bound in $\mathrm{\mid }x\mathrm{\mid }$. At level zero all these operations are deterministic polynomial-time loops.

For positive $k$, conjunctions use a tuple of independent variables at each quantifier block and the conjunction of the matrix tests. The identities $(QaU(a))\wedge (QbV(b))⟺Q(a,b)(U(a)\wedge V(b))$ hold for either quantifier over nonempty domains. One verifies the universal identity by fixing an arbitrary value of the other variable, and the existential identity by combining witnesses. Repeated application proves both directions of the tuple construction. A tuple contains only polynomially many polynomial-length strings.

Disjunction follows by complementing a conjunction of complements; this simultaneously proves closure for both starting polarities. Negating a quantified predicate flips every quantifier and negates its deterministic matrix. A zero-term conjunction is true and a zero-term disjunction is false, both deterministic. Length-zero blocks still have one value.

Append an unused last block for containment in the next level of the same polarity; prepend an unused opposite block for the other polarity. Both preserve truth because binary-string domains are nonempty. The proof copies calls to a fixed base oracle verbatim, so all constructions relativize.

A first-level existential predicate is a polynomial-time verifier with a polynomial-length certificate, so it defines an NP language. Conversely, encode a bounded-length verifier certificate by a length field and padding; a total decoding onto all allowed certificates preserves existence and gives the first-level predicate. This includes length zero and the empty input.

Negating that existential formula yields a universal formula for the complement. Conversely negating a universal formula yields an NP verifier. By the definition of coNP these are exactly the languages of ${\mathrm{\Pi }}_1^p$.

Compile the fixed machine that first applies the stated total decoder and then evaluates $R$ at the exact encoded-pair length determined by $\mathrm{\mid }x\mathrm{\mid }$ and the fixed bound; then fix the bits of $x$. The decoder is polynomial-time and never changes $R$ by silently padding its argument. A halting logspace uniformity procedure on polynomial-length gate indices has polynomially many configurations and hence runs in polynomial time; enumerating the polynomially many gates therefore takes polynomial time. Use the NOT, binary AND/OR and constant basis.

Introduce a variable for every gate output. For $z=a\wedge b$, use $(\mathrm{\neg }z\vee a)\wedge (\mathrm{\neg }z\vee b)\wedge (z\vee \mathrm{\neg }a\vee \mathrm{\neg }b)$; for $z=a\vee b$, use $(z\vee \mathrm{\neg }a)\wedge (z\vee \mathrm{\neg }b)\wedge (\mathrm{\neg }z\vee a\vee b)$; for $z=\mathrm{\neg }a$, use $(z\vee a)\wedge (\mathrm{\neg }z\vee \mathrm{\neg }a)$. Constants use unit clauses. If necessary add an output gate copying the designated input via two negations. Let $C$ be the conjunction. Each assignment to the inputs extends uniquely to one assignment satisfying $C$, by gate order.

With output variable $o$, set $F_{\mathrm{\exists }}=C\wedge o$ and $F_{\mathrm{\forall }}=\mathrm{\neg }(C\wedge \mathrm{\neg }o)$. If $R$ is true, the unique consistent extension witnesses the first formula and every extension satisfies the second. If $R$ is false, no extension satisfies the first and the consistent extension falsifies the second. Negating the 3CNF $C\wedge \mathrm{\neg }o$ gives a 3DNF of the same linear size. Constant predicates and zero input bits obey the same construction.

Parse the encoding deterministically; reject a malformed word. For a well-formed formula, quantify one polynomial-length assignment string per block and evaluate the matrix in polynomial time. Make the parsing test a conjunction in the matrix, so rejection remains valid for either starting polarity. This proves membership even when blocks have length zero.

Given a language at the desired level, take its fixed defining predicate. For each input $x$, apply the pointwise encoding to the whole tuple of quantified strings. If its last block is existential, use $F_{\mathrm{\exists }}$ and merge $z$ into that block. If it is universal, use $F_{\mathrm{\forall }}$ instead. For every assignment to earlier blocks the replacement has exactly the original truth value, so iterating the outer quantifiers preserves truth in both directions.

There are still $k$ blocks and polynomially many symbols; compilation is polynomial-time. It outputs a well-formed instance on every input, with membership equivalent to the original language, which is exactly the required reduction. The construction applies separately to both starting polarities, including $k=1$.

Use the oracle-independent polynomial clock to bound the branch string, number and lengths of queries, and the entire transcript. Guess in a first existential block a branch and all answers to $B$ queries. Replay the machine using these answers, making any $A$ calls directly; reject if the replay does not accept. Thus the replay test is in $P^A$.

Write $B(q)=\mathrm{\exists }{u}_1\mathrm{\forall }{u}_2\cdots Q_k{u}_{k}R(q,u_1,\dots ,u_k)$ with $R\in P^A$. For each guessed YES answer, guess its $u_1$ in the first block too; its remaining condition starts universally and has $k-1$ blocks. For each NO answer, use the complementary $k$-block universal-first formula. Pad YES conditions with an unused last block, and combine the conditions in parallel into $k$ alternating universal-first blocks by tuple conjunction closure. Unused transcript slots impose the constant true condition. At $k=1$, a YES condition has no remaining quantified variable.

An actually accepting branch supplies its correct transcript and YES witnesses, so the constructed formula is true. Conversely a true formula certifies every YES and every NO answer, and the replay is therefore an actual accepting branch. Tuple lengths are polynomial because both query count and query length are polynomially bounded. Prefixing the guessed first block gives exactly $k+1$ alternating blocks over $P^A$. For the unrelativized assertion take $A=\mathrm{\varnothing }$.

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$.

For $L\in {\mathrm{\Sigma }}_k^p$, query oracle $L$ once on the input. For $L\in {\mathrm{\Pi }}_k^p$, query its complementary ${\mathrm{\Sigma }}_k^p$ language and flip the answer. Both are deterministic polynomial-time oracle deciders, proving the first containment for every $k$.

For $k\ge 1$, let $L\in P^B$ with $B\in {\mathrm{\Sigma }}_k^p$. Its deterministic machine is also a nondeterministic machine, so $L\in {\mathrm{\Sigma }}_{k+1}^p$ by [F4]. Reversing its accepting and rejecting outcomes gives a deterministic $B$-oracle decider for the complement; hence the complement is in ${\mathrm{\Sigma }}_{k+1}^p$ as well, and $L\in {\mathrm{\Pi }}_{k+1}^p$ by [F3]. For $k=0$, replace each query to the fixed P oracle by its polynomial-time decider. Polynomial query lengths and counts keep the total time polynomial, so $P^P=P$, and [F3] places it in both first-level classes.

For any language at a fixed quantifier level, evaluate its quantified predicate by enumerating block assignments depth first. Keep one assignment and enumeration counter for each of the finitely many blocks, plus the polynomial workspace of the matrix decider. Existential blocks OR their child values and universal blocks AND them; a length-zero block has the one empty assignment. The resulting finite computation halts on every input, including false predicates. Because the level and length polynomials are fixed for the language, all input and work cells together number at most a polynomial in input length. Level-zero polynomial-time computation also uses polynomial space.

Step 1.3 places each fixed-level language in some DSPACE$(n^c)$, hence in the stated PSPACE union. Taking the union over levels gives PH contained in PSPACE, while steps 1.1--1.2 give all displayed level containments.

A language in ${\mathrm{\Sigma }}_{k+1}^p$ has a leading existential block followed by a ${\mathrm{\Pi }}_k^p$ predicate on the pair consisting of the input and that block. By hypothesis this single language of pairs has a uniform ${\mathrm{\Sigma }}_k^p$ definition. Substitute it and merge its first existential block with the leading one. Because $k\ge 1$, this gives $k$ blocks with polynomial bounds. No input-dependent selection of machines is made.

The reverse containment follows by dummy-block padding. Complement the containment just proved; complements interchange the two polarities, and the assumed level is complement closed. Consequently both classes at level $k+1$ equal ${\mathrm{\Sigma }}_k^p$. Zero-length witness blocks remain nonempty domains.

Start at level $k$ and repeatedly apply the propagation lemma. After each application the next two polarities equal the same class, so the hypothesis needed for the following application holds. By finite induction all levels at least $k$ equal ${\mathrm{\Sigma }}_k^p$; lower levels embed by unused quantifier blocks. Taking their union proves the first assertion.

If $P=NP$, a one-block existential verifier defines a P language, and every P language has an unused existential witness. Deterministic P is complement closed by flipping a halting decider's bit, so ${\mathrm{\Sigma }}_1^p={\mathrm{\Pi }}_1^p=P$. Apply the first assertion at level one. Empty inputs and unused witnesses cause no exception.

Choose a fixed $k\ge 1$ with $C\in {\mathrm{\Sigma }}_k^p$, padding upward if necessary. Every $L\in {\mathrm{\Pi }}_k^p$ belongs to PH by padding and reduces to $C$, hence lies in ${\mathrm{\Sigma }}_k^p$ by preimage closure. Complementing gives the reverse inclusion, so the finite-level collapse theorem applies.

Under $\mathrm{P}\mathrm{H}=\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$, TQBF belongs to PH and every PH language reduces to it, by its exact PSPACE-completeness statement. It therefore serves as $C$ in the first step. No strict containment between PH and PSPACE is assumed.

A polynomially clocked branch is encoded by polynomially many bits; a deterministic $A$-verifier replays it with the original oracle queries. Conversely a nondeterministic machine guesses the verifier witness and executes that verifier. A deterministic machine is a special case. All query writing is charged.

The relative oracle characterization is supplied with access to that same base oracle. For space containment, use the depth-first assignment evaluation from the unrelativized containment proof; each matrix predicate makes only polynomial-length $A$ queries and uses polynomial space including the query tape. Query buffers are reused. This treats both starting polarities and hence NP and coNP as well.

For collapse, substitute a uniform ${\mathrm{\Sigma }}_k^{p,A}$ definition for the inner ${\mathrm{\Pi }}_k^{p,A}$ language of pairs and merge existential blocks. The final predicate still lies in $P^A$; no new oracle is introduced. Complementation flips its answer and preserves $A$. Iterate this argument over the finite levels, then take their union. Zero-length blocks and immediately halting computations are preserved in each simulation.

Choose $n$ larger than every committed word length, with $2^n>p(n)$. Such integers exist: for a fixed degree $a$, the ratio $(n+1{)}^a\mathrm{/}{2}^{n+1}$ divided by $n^a\mathrm{/}{2}^n$ tends to $1\mathrm{/}2$, and is eventually bounded below one, so any polynomial is eventually smaller than $2^n$. Simulate the clocked machine; answer committed queries consistently and commit every previously unassigned queried word to NO. The clock bounds both query length and count.

If it accepts, commit all $n$-bit words to NO. If it rejects (including clock expiration), choose an unqueried $n$-bit word and commit it to YES, committing every other $n$-bit word to NO. There is an unqueried word because fewer than $2^n$ queries occurred and no earlier commitment had length $n$. Each extension is finite and consistent.

Every total extension retains all answers on the simulated path, including queries longer than $n$, so the deterministic path is unchanged. In the accepting case $1^n\mathrm{\notin }{L}_B$; in the rejecting case $1^n\in L_B$. Thus both outcomes defeat the machine for every total extension.

Enumerate all deterministic oracle programs paired with clocks $(n+2{)}^a+a$, for positive integers $a$. Every polynomial-time oracle decider agrees with some clocked program for its oracle. Starting with no commitments, apply the finite-extension lemma once to each pair, always preserving all prior commitments. Let $B$ have precisely the words ever assigned YES; all other words receive NO. This is a consistent total extension of every stage.

At the assigned input the corresponding clocked program fails by the lemma, so no polynomial-time $B$ decider decides $L_B$. A nondeterministic machine rejects nonunary inputs, guesses one $n$-bit word on $1^n$, and asks whether it belongs to $B$. It accepts exactly $L_B$ within polynomial time; at $n=0$ it queries the empty word. Thus the separation follows.

For a nondeterministic oracle machine with clock $p(n)$, enumerate all branch-choice strings of the bounded length and replay each branch. Each TQBF query has length at most $p(n)$ under the charged-query convention. Decide it by the polynomial-space algorithm supplied by TQBF membership in PSPACE, then reuse that workspace. A branch counter, a machine configuration and the query workspace all have polynomial size; accepting when one replay accepts yields a deterministic polynomial-space decider. Zero-query branches use the same procedure.

For any PSPACE language, its polynomial-time many-one reduction to TQBF computes one polynomial-length query. Accept exactly when the oracle answers YES. This is a deterministic polynomial-time oracle decider on every input, proving the other containment.

Oracle absorption supplies $\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}\subseteq P^A$ and $N{P}^A\subseteq \mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$. A deterministic oracle computation is a nondeterministic one with no choices, so $P^A\subseteq N{P}^A$.

The inclusions form a closed chain, giving equality of all three classes. The same fixed total TQBF language is used throughout; it is not required to belong to P.

By the definition of relativization, an argument for equality with this property would prove $P^B=N{P}^B$ for every total $B$. The separating oracle supplies a counterinstance.

An argument for inequality with this property would prove $P^A\mathrm{\ne }N{P}^A$ for every total $A$. The TQBF oracle instead gives equality. These two obstructions concern the property of the argument, and imply neither an unrelativized equality nor an unrelativized separation.

If $P^A=P$, one query decides $A$, so $A\in P$. Conversely a P decider for $A$ replaces each of polynomially many polynomial-length queries, giving $P^A=P$. This proves the level-zero low identity under the restriction $A\in NP$.

If $N{P}^A=NP$, deterministic queries decide both $A$ and its complement in $N{P}^A$, so $A\in NP\cap coNP$. Conversely assume both have NP verifiers. Guess an accepting branch and its adaptive query transcript, and an appropriate NP witness for every YES or NO answer. Deterministic replay and verification accepts exactly the real accepting transcripts; the total certificate length is polynomial. Therefore $N{P}^A\subseteq NP$, while ignoring the oracle gives the reverse containment. The first-level identity identifies this with lowness at level one.

Every $A\in NP$ has a polynomial-time many-one reduction to SAT, so $P^A\subseteq P^{SAT}$. Equality implies $SAT\in P^A$, which implies every NP language belongs to $P^A$ by composing its SAT reduction. Conversely that Turing completeness gives $SAT\in P^A$ and allows every SAT query to be simulated using $A$, proving $P^{SAT}\subseteq P^A$. These reductions use the first-level complete language in the highness convention.

For $k\ge 1$, the relative oracle characterization gives ${\mathrm{\Sigma }}_{k+1}^{p,A}=N{P}^{{\mathrm{\Sigma }}_k^{p,A}}$: the base oracle may be absorbed into the inner language by a tagged union, since $A\in P^A\subseteq {\mathrm{\Sigma }}_k^{p,A}$ and that class is closed under tagged unions. For $k=0$ the same identity holds as $N{P}^{P^A}=N{P}^A$, by replacing each $P^A$ subroutine with its deterministic oracle simulation. Thus equality of the inner classes, either with the unrelativized class or with the SAT-relativized class, propagates one level. This proves both nestings, including the zero-to-one transition. Empty transcripts and constant oracles are included by these simulations.

There exists a total $B$ with $P^B\mathrm{\ne }N{P}^B$, so the premise of the proposed rule is realized.

For $A=TQBF$, however, $P^A=N{P}^A$. This violates the universally quantified conclusion and refutes the rule. The isolated implication from the separating world to $P\mathrm{\ne }NP$ is not here called a known false proposition: determining its truth would require settling the unrelativized question.