Theodore Baker

contemporaryAnalytic Philosophy / Computational Complexity Theory

b. 1949

Theodore Baker is an American computer scientist best known for his contributions to computational complexity theory. He is most famous for the Baker-Gill-Solovay theorem, which demonstrated that the P vs NP question cannot be resolved by relativizing proof techniques.

Notable Achievements

Co-authored the Baker-Gill-Solovay theorem (1975) showing oracle-relative separations of P and NP

Established foundational limits on proof techniques in computational complexity

Contributed to the theory of relativized computation

Published influential work on real-time computing and Ada programming language semantics

Positions & Arguments(1)

Skepticism

claim

There is a fundamental tension between treating logical knowledge as a priori and the computational intractability of deciding logical validity.

Truth & Knowledge

claim

There is a fundamental tension between treating logical knowledge as a priori and the computational intractability of deciding logical validity.