John Gill
John Gill is an American theoretical computer scientist whose 1975 paper with Theodore Baker and Robert Solovay — the Baker–Gill–Solovay theorem — fundamentally reshaped the P versus NP problem and the methodology of computational complexity theory. The theorem demonstrated that the P = NP question cannot be resolved by any proof technique that relativizes: there exist oracles A and B such that PA = NPA and PB ≠ NPB. This result established that the deepest question in computer science requires non-relativizing techniques — a constraint that continues to guide complexity research half a century later.
The Baker–Gill–Solovay Theorem
The theorem addresses a methodological puzzle. Since the 1960s, complexity theorists had used diagonalization — the technique that Cantor used to show the reals are uncountable and that Turing used to prove the Halting Problem undecidable — to establish separation results. Diagonalization is a powerful, almost universal proof technique in computability theory. Could it solve P versus NP?
Baker, Gill, and Solovay showed that the answer is no, at least for a broad class of diagonalization-style arguments. An oracle machine is a Turing machine with access to an "oracle" — a black-box subroutine that answers membership queries for some set A in a single step. The complexity classes P and NP can be relativized to any oracle: PA is the class of problems solvable in polynomial time by a machine with oracle A; NPA is the analogous nondeterministic class.
The theorem constructs two oracles:
- Oracle A (the "collapsing" oracle): A cleverly constructed set A such that PA = NPA. This oracle makes the polynomial hierarchy collapse at the first level.
- Oracle B (the "separating" oracle): A set B such that PB ≠ NPB. This is constructed by diagonalization against all polynomial-time machines with oracle access.
The striking conclusion: any proof that P = NP or P ≠ NP must be non-relativizing. If a proof works relative to all oracles, it cannot be correct — because it would have to yield both conclusions simultaneously.
Implications for Complexity Theory
The Relativization Barrier
The Baker–Gill–Solovay theorem is the first of three major barriers in complexity theory. The second is the Natural Proofs barrier (Razborov and Rudich, 1994), which shows that certain circuit lower-bound techniques cannot work unless strong cryptographic assumptions fail. The third is the algebrization barrier (Aaronson and Wigderson, 2008), which extends relativization to algebraic oracles.
These barriers are not merely technical obstacles. They reveal a deep structural feature of complexity theory: the separation of complexity classes requires proof techniques that are sensitive to the specific structure of computation, not merely to its abstract closure properties. Any technique that treats computation as a black box — whether through oracles, circuits, or algebraic extensions — is insufficient.
The Role of Diagonalization
Gill's work raises a foundational question about the limits of diagonalization. Diagonalization works by constructing an object that differs from every object in a countable list — a technique that seems universally applicable. But the relativization barrier shows that diagonalization, when applied to complexity classes relative to oracles, is too powerful: it can construct oracles that make P ≠ NP hold, but also oracles that make P = NP hold. The technique is oracle-dependent, not absolute.
This connects to broader issues in metamathematics and proof theory. Just as Gödel's incompleteness theorems show that sufficiently strong formal systems cannot prove their own consistency, the relativization barrier shows that sufficiently abstract proof techniques cannot resolve concrete complexity questions. The barrier is a complexity-theoretic incompleteness theorem.
Connections to Philosophy of Mathematics
The Baker–Gill–Solovay theorem has surprising philosophical implications. It suggests that the P versus NP problem is not merely a technical question about algorithms but a foundational question about the nature of mathematical proof. If the problem requires non-relativizing techniques, and if such techniques must exploit the specific combinatorial structure of computation rather than its abstract properties, then the resolution of P versus NP may require a new kind of mathematical insight — one that we do not yet possess.
This resonates with debates in philosophy of mathematics about the nature of mathematical objects and the limits of formalization. The oracle construction in the Baker–Gill–Solovay theorem is reminiscent of Paul Cohen's forcing technique in set theory, which showed that the Continuum Hypothesis is independent of ZFC. Both results use model-theoretic techniques (oracles / generic extensions) to demonstrate the independence of a statement from a class of proof methods. The Baker–Gill–Solovay theorem is, in a sense, complexity-theoretic forcing.