The Polynomial Hierarchy and Relativization: Examples and Counterexamples

A formula is satisfiable exactly when some assignment makes its polynomial-time evaluation true, and is a tautology exactly when all assignments do. These are first-level predicates, with completeness for the corresponding bounded-QBF encodings. A formula with no variables has one assignment.

For valid $0\le k\le n$, let $I_j(S)$ test that an $n$-bit indicator represents an independent set of cardinality $j$. Then the exact condition is $\mathrm{\exists }S\mathrm{\forall }T[I_k(S)\wedge \mathrm{\neg }{I}_{k+1}(T)]$. Reversing the two independent blocks gives the same truth value: in the reverse direction fix any $T$ to obtain a witness $S$, and every $T$ must fail $I_{k+1}$. If both conditions hold one witness $S$ works for every $T$. At $k=0$ the empty set witnesses $I_0$; at $k=n$, $I_{n+1}$ is always false. This also covers the graph with no vertices. A deterministic validity test in the matrix rejects all malformed and out-of-range inputs for either polarity.

A branch has at most polynomially many queries, all of polynomial length. Replaying the finite branch tree and deciding each TQBF query in reusable polynomial space gives the absorption; one many-one TQBF reduction supplies the converse PSPACE inclusion into deterministic oracle time.

At $n=8$ there are $256$ candidate words and at most $64$ queries. Preserve earlier commitments and answer every new query NO. At least $192$ length-eight words remain unqueried. An accepting run is defeated by freezing the entire length to NO; a rejecting run by setting one unqueried word YES and freezing the rest NO. Also freeze every queried word of other lengths. Further stages are required to defeat other programs. Opposite full oracle worlds, not this one finite count alone, yield the relativization obstruction.

Use the separating oracle $B$ and the equality oracle $A=TQBF$ in the refutation of the schema. They satisfy $P^B\mathrm{\ne }N{P}^B$ and $P^A=N{P}^A$, respectively. Thus the premise holds while one instance of the universal conclusion fails.

The empty oracle is a third specified world. The exhibited failure at $A$ establishes invalidity of universal transfer, but gives no equality or inequality for the empty oracle. Hence this counterexample does not resolve the ordinary P-versus-NP problem.

Both $B_0=\{0\}$ and $B_1=\{0,00\}$ are total membership completions respecting $Y^{\mathrm{\prime }}$ and $N^{\mathrm{\prime }}$. They disagree on the off-promise word $00$. Their unspecified words are simply NO membership answers.

Take the source pair $(\{0\},\mathrm{\varnothing })$. On input $0$ the caller rejects with $B_0$ and accepts with $B_1$. Universal correctness over completions therefore fails at a promised YES input, despite the caller's constant running time. No source-NO obligation is needed for this failure.