Motivation
An oracle machine can ask whether a string belongs to a fixed set and receive the answer in one step. Oracles are a mathematical way to give two kinds of machines the same extra information, then ask which relations between their complexity classes follow from a proof technique. If a technique works unchanged with every oracle, a single argument of that type cannot establish an answer that fails in one oracle world.
We will construct an oracle relative to which deterministic and nondeterministic polynomial time differ, and use a PSPACE-complete oracle to obtain a world in which they agree. The constructions are about relativized classes. They do not decide the ordinary P versus NP question.
Definitions
Definition 4.4.1
(Oracle machines and relativized classes)
An oracle is a fixed set. A deterministic oracle machine may write a query string and receive one answer bit indicating membership in ; a nondeterministic oracle machine may also branch. The time bound includes writing the query, and an oracle answer costs one step. Thus a machine running for steps cannot write a query longer than .
Write and for the languages decided by deterministic and nondeterministic polynomial-time machines with the same oracle . The oracle is not required to be computable for these definitions, although the separating construction below can be made computable. The empty oracle recovers the ordinary machine model up to a trivial simulation.
We use polynomial-space completeness of true quantified Boolean formula, TQBF, from the companion space chapter. In particular TQBF is in PSPACE, and every PSPACE language has a deterministic polynomial-time many-one reduction to it. We do not reprove that completeness theorem here.
Theorem
Theorem 4.4.2
(Two different oracle outcomes)
There are oracles and such that
The first separation and the second equality are statements about different fixed oracles, not a contradiction about the unrelativized classes.
The main work is to build while ensuring that later stages do not change answers observed by earlier simulated machines. We then take to be TQBF.
Constructing a separating oracle
For an oracle , define the unary language
It belongs to : on input , nondeterministically guess an -bit string and ask the oracle once. Reject strings that are not unary. The witness is the queried string, and writing it takes time.
Proof
(Diagonalizing against every clocked oracle machine)
Effectively enumerate pairs consisting of a deterministic oracle program and an integer . For the th pair, let be that program forcibly stopped after
steps on inputs of length , with timeout treated as rejection. Every deterministic polynomial-time oracle machine appears with a sufficiently generous clock: increasing the exponent absorbs its fixed polynomial degree and constants. Every halts on every oracle and input.
Build a finite set at stage , starting with . Also remember the lengths of all strings queried in earlier stage simulations. Choose larger than every earlier selected length and every earlier query length, and large enough that
Such a length exists because a fixed polynomial grows more slowly than . Simulate on input using the provisional oracle : answer yes exactly for strings already in that finite set, and answer no to every other query. Let be the finite set of strings queried during this simulation.
If accepts, set : no string of length is added. If it rejects, choose an -bit string and set . Such a string exists because the simulation makes at most queries. Define the final oracle by .
The rejected-case addition does not change the simulation's answers, because was not queried. Later stages add strings only at lengths larger than every query length recorded so far, so they also cannot change any answer seen in this stage. The completed-oracle computation of on is therefore exactly the simulated one. Earlier added strings have length less than , and later added strings have length greater than . Thus, in the accepting case, no -bit string is in and ; in the rejecting case, and . In both cases is wrong on that input.
Every deterministic polynomial-time oracle machine occurs in the enumeration with an adequate clock, so none decides . Since , this proves .
The choices can be made effective: take the least satisfying the stated bounds and, when needed, the lexicographically first eligible . Each stage is finite because the simulated machine is clocked and the provisional oracle is finite. To decide whether a given string belongs to , run stages until the selected length reaches or exceeds its length; strict increase guarantees this happens, and later stages cannot add a string of that length. Thus this particular construction can give a computable oracle, even though computing it is not part of the polynomial-time oracle-machine model.
Proof X-ray
Protect the queries, not only the diagonal length
Choosing later diagonal lengths larger than earlier selected lengths is not enough: an earlier machine might have queried a much longer string. The construction records every query length and chooses all later insertion lengths above that maximum. In the rejecting case it also chooses an unqueried string at the current length. These two protections keep the simulated transcript unchanged in the final oracle.
Worked examples
Worked example 4.4.3
(One finite stage)
Suppose a simulated machine on makes fewer than sixteen queries and rejects. Among the sixteen four-bit strings, at least one was not queried. Adding such a string makes the unary input belong to while preserving every answer the machine just saw. This is a finite illustration; an actual stage must also choose its length larger than all previously protected query lengths and satisfy its particular clock inequality.
Worked example 4.4.4
(Why a longer query must be protected)
At a stage using input length four, a machine might query a ten-bit string. If a later stage were allowed to add that very ten-bit string, the earlier simulation could change from a no-answer to a yes-answer and its recorded output might no longer be valid. Requiring the next insertion length to exceed ten prevents this particular injury. Protecting the input length four alone would not.
Worked example 4.4.5
(Existence of an unqueried witness)
If a simulation asks at most distinct queries of length , it cannot inspect all seven-bit strings. A string outside the queried set can be selected. The proof uses the number of possible witnesses at the chosen length, not an assumption that the machine's oracle queries are independent or random.
Counterexample mode
Why the length must beat the clock
Claim: the diagonal stage works at any input length, so the inequality is a technicality. Take and the machine that queries all eight -bit strings and accepts exactly when some answer is yes. Checking all choices of shows that it accepts exactly when , so it is correct at this length for every oracle and no string can be added to defeat it. The machine needs only about steps, which is why the stage must choose with , leaving a string unqueried.
An oracle that makes the classes equal
Theorem 4.4.6
(A PSPACE-complete oracle)
Let . Then
Proof
(The two inclusions through TQBF)
Because TQBF is PSPACE-complete under polynomial-time many-one reductions, every PSPACE language can be decided by a polynomial-time machine that computes its reduction and makes one query to . Hence .
For the other direction, simulate a polynomial-time nondeterministic -oracle machine in polynomial space. Along any branch it writes only polynomially many symbols and makes polynomially many queries, each of polynomial length. To answer a query, run the deterministic PSPACE algorithm for TQBF, reusing its work area afterward. Explore the nondeterministic computation tree depth first and accept if some branch accepts. A stack of polynomially many polynomial-size configurations plus one polynomial-space oracle computation uses polynomial space, although the simulation may take exponential time. Thus .
The trivial containment completes the chain of inclusions and proves equality. The word “oracle” is essential: the polynomial-time machine is granted unit-cost membership answers for TQBF; the proof does not put TQBF in ordinary P.
Worked example 4.4.7
(A PSPACE computation as one oracle question)
Given a PSPACE language , let be its polynomial-time reduction to TQBF. On input , the oracle machine computes , asks whether it is true, and returns that answer. The reduction and query construction are polynomial in ; the oracle answer is supplied by the model. This explains the lower inclusion without claiming an ordinary polynomial-time TQBF algorithm.
What the two constructions mean
A proof that remains valid after replacing all machines and classes by their versions relative to an arbitrary fixed oracle is called relativizing in this discussion. If one uniform proof established for every oracle , it would contradict the separating oracle. If it established for every oracle , it would contradict the equality oracle. Thus a proof that resolves the unrelativized question cannot have either of those universally relativizing forms.
This is a limitation on a proof strategy, not a proof that P versus NP is independent of the usual axioms, and not a claim that diagonal arguments are useless. A proof can use features that do not persist under arbitrary oracle access. The theorem also does not assert the same outcome for all oracles: its force comes from exhibiting two different choices.
Common mistakes
Common mistake
(Queries can be longer than the input)
A deterministic polynomial-time machine may query strings longer than its input, so preserving only earlier input lengths is insufficient in the separating construction. The inequality guarantees an unqueried string at the selected length; it does not say that the machine cannot query longer strings.
Common mistake
(Oracle statements are about fixed oracles)
gives the nondeterministic machine the same oracle as the deterministic machine. Oracle equality or separation does not automatically transfer to the empty-oracle case.
Summary
A diagonal construction adds at most one carefully chosen oracle string per stage and protects all earlier query lengths, placing a unary witness language in . A PSPACE-complete oracle gives the opposite equality. Together the two worlds show why a uniform all-oracle argument cannot resolve P versus NP.
Exercises
Quick check
(Why is in for every oracle ?)
Solution · Answer
On input , guess an -bit witness and query it. Accept exactly when the oracle answers yes.
Quick check
(At a rejecting stage, why must there be an unqueried string of the selected length? Why does adding that unqueried string preserve the current simulation?)
Solution · Answer
There are strings of that length and fewer than total queries, so at least one was not queried. The new string was absent from the queried set, so every query in the deterministic simulation receives the same answer after the addition.
Quick check
(Why must later insertion lengths exceed earlier query lengths, not just earlier selected input lengths?)
Solution · Answer
A machine can query strings longer than its input. A later insertion at such a length might change an answer in the earlier transcript.
Quick check
(If the simulated machine accepts at a stage, how is the oracle chosen at that selected length?)
Solution · Answer
No string of that selected length is added. Earlier and later insertions have different lengths, so the final oracle has none there.
Quick check
(Why does TQBF completeness imply ? Why is ?)
Solution · Answer
Compute the polynomial-time reduction to TQBF and make one oracle query. The model supplies the answer in one step. Explore the polynomial-time nondeterministic computation tree depth first and answer each polynomial-length TQBF query with a reusable polynomial-space algorithm.
Quick check
(Does the separating oracle prove ordinary ? Does the existence of two oracle outcomes show that P versus NP is independent of standard axioms?)
Solution · Answer
No. It proves a separation only when both classes are equipped with the constructed oracle. No. It limits proof arguments that remain valid relative to every oracle; it is not a formal independence theorem for the ordinary question.
Quick check
(Why is it legitimate to enumerate clocked pairs of programs and polynomial exponents?)
Solution · Answer
Every polynomial-time oracle machine has some polynomial time bound. A sufficiently large fixed exponent gives a clock that dominates that bound, and every program–exponent pair can be enumerated.
Quick check
(What information must a stage preserve before choosing all later lengths?)
Solution · Answer
It must record all query lengths used in the current simulation, together with earlier protected lengths, so future insertions avoid every earlier queried string.