A researcher claims to have proved that every NP problem can be solved in polynomial time by a deterministic Turing machine. Their proof technique works by constructing a simulation that applies identically regardless of which oracle is attached to both the NP machine and the deterministic machine. What does the Baker-Gill-Solovay theorem tell us about this proof?
AThe proof is valid — Baker-Gill-Solovay only applies to nondeterministic proof techniques, not deterministic simulations
BThe proof conclusively establishes that P = NP, which is consistent with Baker-Gill-Solovay's findings
CThe proof must contain an error, because any technique that works the same way with any oracle cannot resolve P vs NP — different oracles give opposite answers
DThe proof proves P = NP only for the specific oracle used in constructing the simulation
Baker-Gill-Solovay showed that there exist oracles A and B such that P^A = NP^A and P^B ≠ NP^B. A proof technique that applies 'identically regardless of which oracle is attached' is, by definition, relativizing. But a relativizing proof would work equally well with oracle A (where the conclusion P=NP would be correct) and with oracle B (where the same proof would need to establish P=NP, but P^B ≠ NP^B). This contradiction shows no relativizing technique can settle P vs NP — so the researcher's proof must fail somewhere.
Question 2 Multiple Choice
What does the notation P^A represent in complexity theory?
AThe class of languages in P that can be many-one reduced to set A in polynomial time
BThe class of languages decidable in polynomial time by a deterministic machine with free oracle access to set A — membership queries to A cost one step
CThe class of problems that become harder than polynomial time when oracle A is not available
DThe set of languages A for which polynomial-time machines can verify solutions
M^A denotes a Turing machine M augmented with an oracle for set A. When the machine writes a string w on the oracle tape and enters the query state, it transitions to 'yes' or 'no' in one step depending on whether w ∈ A. P^A is the set of all languages decidable by a deterministic polynomial-time machine with such oracle access. The oracle does not make the machine nondeterministic, and it does not change the machine's own transition rules — it just provides free answers to one specific decision problem.
Question 3 True / False
The existence of an oracle A such that P^A = NP^A constitutes evidence that P = NP in the unrelativized setting.
TTrue
FFalse
Answer: False
Oracles fundamentally change the computational environment. The statement P^A = NP^A tells you something about what machines can do *when given free access to A* — it does not transfer to the world without oracles. Indeed, Baker-Gill-Solovay also showed that there exists oracle B such that P^B ≠ NP^B. You cannot infer from either oracle result anything about the unrelativized question P vs NP. Oracles are tools for understanding proof techniques (by showing what relativizing techniques can and cannot prove), not for resolving the underlying complexity question.
Question 4 True / False
Baker, Gill, and Solovay's result implies that any proof of P ≠ NP must use proof techniques that behave differently depending on which oracle is attached to the machines.
TTrue
FFalse
Answer: True
This is the precise implication of their result. A relativizing proof technique is one that applies the same way regardless of the oracle. BGS showed that relativizing techniques cannot resolve P vs NP — because with oracle A you get P^A = NP^A, while with oracle B you get P^B ≠ NP^B, and a relativizing proof would yield the same conclusion in both cases (a contradiction). Therefore any valid proof of P ≠ NP (or P = NP) must be non-relativizing: it must exploit specific structural properties of the actual TM model that are not preserved when an oracle is added.
Question 5 Short Answer
Why does the Baker-Gill-Solovay theorem (showing that P^A = NP^A and P^B ≠ NP^B for different oracles A and B) establish that diagonalization arguments alone cannot resolve the P vs NP question?
Think about your answer, then reveal below.
Model answer: Diagonalization is a relativizing technique — the diagonal argument proceeds in the same structural way whether or not both machines have an attached oracle. But BGS shows the answer to 'P vs NP' changes with the oracle: for oracle A the classes are equal, for oracle B they are not. If diagonalization could prove P=NP (or P≠NP), the same argument would apply with any oracle, forcing the same answer for every oracle. Since different oracles give different answers, no single relativizing argument can be correct for all of them — the technique is too coarse to capture the distinction.
This result was transformative because it ruled out an entire family of proof strategies all at once. Before BGS, many researchers hoped that the techniques used to prove Turing's undecidability results (which are essentially diagonalization arguments) could be adapted to separate complexity classes. BGS showed this hope was misplaced. Modern breakthroughs in complexity — like IP=PSPACE, which uses arithmetization (a non-relativizing technique) — succeeded precisely by finding approaches that do not relativize.