A researcher proposes to prove P ≠ NP by constructing a diagonalization argument: enumerate all polynomial-time algorithms, and for each one, construct an input on which the algorithm fails. Baker, Gill, and Solovay's theorem implies this proof strategy:
AIs valid and would definitively settle P ≠ NP if carried through correctly
BCannot succeed, because diagonalization is a relativizing technique and there exist oracles where P = NP — any relativizing proof would prove P = NP under that oracle, contradiction
CWorks only for NP-complete problems, not for all problems in NP
DRequires an oracle for the halting problem to construct the diagonalization
Baker, Gill, and Solovay showed that there exists an oracle A where P^A = NP^A. A diagonalization argument is relativizing — it works the same way in any oracle model. If the proposed diagonalization succeeded and proved P ≠ NP, then relativized under oracle A it would prove P^A ≠ NP^A. But P^A = NP^A by construction, giving a contradiction. Therefore no relativizing argument can prove P ≠ NP (or P = NP). This does not mean P ≠ NP is unprovable — it means the proof must use non-relativizing techniques that somehow exploit the specific structure of the computation.
Question 2 Multiple Choice
What is K' (the halting problem relativized to K), and how does it relate to K in the computability hierarchy?
AK' is identical to K — relativizing the halting problem to itself yields the same problem
BK' is strictly harder than K — it is the halting problem for oracle Turing machines with oracle K, and no TM equipped with oracle K can decide K'
CK' is easier than K because oracle access to K can be used to partially solve its own halting problem
DK' is the complement of K — it decides exactly which TMs with oracle K do NOT halt
K' = {⟨M, x⟩ : M^K halts on x} is the halting problem for TMs equipped with oracle K. A TM with oracle K can decide many things K alone cannot — for example, the totality problem 'does M halt on every input?' is computable from K. But K' is strictly harder: it encodes questions about the halting behavior of K-oracle machines, which go one level beyond what K can answer. No TM with oracle K can decide K'. This strict hierarchy — K < K' < K'' < ... — constitutes the arithmetical hierarchy, with each level requiring one additional quantifier alternation.
Question 3 True / False
Baker, Gill, and Solovay's theorem implies that any valid proof or disproof of P = NP must use non-relativizing techniques that cannot simply treat computation as a black box.
TTrue
FFalse
Answer: True
This is the direct implication of the BGS result. Since there exist oracles making P^A = NP^A and others making P^B ≠ NP^B, any argument that relativizes — that works the same way with or without an oracle — would produce a contradiction: it would prove the same result in both oracle worlds, but the oracle worlds have opposite answers. Non-relativizing techniques include things like arithmetization (the key to IP = PSPACE) and algebraic methods. The BGS result is a barrier theorem: it rules out entire families of proof strategies without settling the question itself.
Question 4 True / False
The Baker-Gill-Solovay result shows that P = NP is independent of standard set-theoretic axioms like ZFC, meaning the question can seldom be resolved by ordinary mathematical proof.
TTrue
FFalse
Answer: False
This is a common and serious misconception. BGS shows that relativizing proof techniques cannot resolve P vs NP — it constrains the *method* of proof, not the existence of a proof. Independence from ZFC would be a separate and much stronger statement (requiring, for example, a forcing argument or inner model construction), and no such independence result has been proved. P vs NP may well have a definite answer (likely P ≠ NP) that is provable within ZFC using non-relativizing techniques, just as the primality testing problem was eventually resolved. BGS is a barrier, not an impossibility.
Question 5 Short Answer
Explain the difference between 'an oracle makes a TM absolutely more powerful' and 'an oracle makes a TM more powerful relative to a specific problem.' Why does this distinction matter for understanding what oracle results tell us about P vs NP?
Think about your answer, then reveal below.
Model answer: An oracle for problem B gives a TM the ability to answer B-queries in one step — but only questions about B. The TM is more powerful in the specific sense that it can now solve problems reducible to B that it could not solve before. But it is not more powerful in an absolute sense: a K-oracle TM cannot decide all problems, only those reducible to K. Different oracles create different computational landscapes: an oracle for SAT gives P^SAT = NP^SAT (since NP ⊆ P^SAT trivially), while random oracles make P^A ≠ NP^A with probability 1. This oracle-relativity is why BGS constrains proof methods: a proof that treats computation as a black box (relativizing) works the same in all oracle worlds, so it cannot distinguish the world where P = NP from the one where P ≠ NP. The actual P vs NP question is about the unrelativized world — a very specific fixed computational model — and its resolution requires exploiting the concrete structure of that model.
The key insight is that oracles are tools for studying proof techniques and relative computability, not direct evidence about unrelativized complexity classes. When a theorem holds relative to all oracles, it is likely provable by elementary means. When results differ across oracles (like P vs NP), it signals that the question requires techniques sensitive to the specific structure of computation — which is useful information about what kind of proof to look for, even if it does not settle the question.