Theodore Baker
Theodore Baker is an American theoretical computer scientist best known as the co-author, with John Gill and Robert Solovay, of the landmark 1975 Baker–Gill–Solovay theorem — the result that established the relativization barrier in computational complexity theory and demonstrated that the P versus NP problem cannot be resolved by any proof technique that treats computation as a black box. While less prolific in public visibility than some of his co-authors, Baker's contribution to the theorem was foundational in shaping the methodological self-awareness of complexity theory.
The Baker–Gill–Solovay Theorem and Methodological Rigor
The 1975 paper emerged from a period of optimism in complexity theory. Cook's theorem (1971) had established NP-completeness; Karp's subsequent identification of twenty-one NP-complete problems (1972) suggested that the P = NP question was ripe for resolution. Many researchers believed that diagonalization — the technique that had resolved the Halting Problem and countless other undecidability results — would soon separate P from NP.
Baker, Gill, and Solovay demonstrated that this optimism was misplaced. Their theorem showed that diagonalization relative to an oracle cannot separate P from NP — because there exist oracles under which the classes collapse and oracles under which they separate. Any proof that works "for all oracles" would have to yield both conclusions, which is impossible. The result did not rule out all diagonalization approaches, but it ruled out a broad and natural class of them.
What makes the theorem philosophically significant is its meta-methodological character. It is not a result within complexity theory but a result about complexity theory — about what kinds of evidence and proof are adequate to its central questions. Baker's contribution, alongside his co-authors, was to show that complexity theory requires a reflexive understanding of its own tools: the question is not merely "What is the answer?" but "What would count as a proof, and why does this class of proofs fail?"
Complexity Theory as Self-Aware Discipline
The Baker–Gill–Solovay theorem inaugurated a tradition in complexity theory that might be called barrier methodology: the systematic study of why certain proof techniques cannot work. This tradition includes:
- The Natural Proofs barrier (Razborov and Rudich, 1994): certain circuit lower-bound techniques would break pseudorandom generators if they worked.
- The Algebrization barrier (Aaronson and Wigderson, 2008): extensions of relativization to algebraic oracles.
- The Natural Proofs refinement and its connections to cryptographic hardness assumptions.
Baker's work thus stands at the origin of a research program that treats complexity theory not as a collection of open problems but as a reflective discipline — one that studies the limits of its own methods with the same rigor it applies to computational problems. This is structurally analogous to the Gödelian turn in mathematical logic: just as Gödel showed that sufficiently strong formal systems cannot prove their own consistency, the barrier results show that sufficiently abstract complexity techniques cannot resolve their central questions.
Connections to Broader Themes
The Role of Oracles
The oracle construction in the Baker–Gill–Solovay theorem is a technique borrowed from computability theory, where oracles were introduced by Turing and developed by Post. In complexity theory, oracles serve as a controlled counterfactual: they allow researchers to ask "What would complexity look like if we had access to this computational resource?" The Baker–Gill–Solovay result shows that the answer depends sensitively on the oracle — which means that the "real" P versus NP question is about the specific structure of computation without oracles, not about its abstract closure properties.
This has implications for the philosophy of mathematics. If a mathematical question requires techniques that are sensitive to specific structure rather than abstract form, then the question is not merely "mathematical" in the sense of derivable from axioms alone. It may require what Lakatos called "quasi-empirical" methods: heuristic reasoning, pattern recognition, and the gradual refinement of concepts through trial and error. The P versus NP problem may be a natural kind whose resolution requires more than formal deduction — it may require a new conceptual framework that we do not yet possess.
Baker–Gill–Solovay and Scientific Method
From a philosophy of science perspective, the Baker–Gill–Solovay theorem is a falsification of a research program. It does not prove P ≠ NP or P = NP; it proves that a certain approach to proving either cannot succeed. This is structurally similar to how experimental null results function in natural science: they do not confirm a positive hypothesis but they eliminate a class of possible explanations, forcing the research community to explore alternative approaches.
The theorem thus exemplifies what Popper called the asymmetry of falsification: we may not know what will work, but we can know what will not. Baker's contribution, in this light, is part of the error-elimination phase of scientific inquiry — a necessary, if unglamorous, component of theoretical progress.