1927 – 2011
Alan Cobham is a contemporary figure associated with foundational work in computational complexity theory, particularly known for formalizing the notion of tractable computation. His contributions bridge mathematical logic and theoretical computer science, raising questions about the epistemological status of logical and mathematical knowledge in light of computational constraints.
Formulated Cobham's thesis identifying feasible computation with polynomial-time complexity
Contributed to the theory of computational complexity and tractability
Explored tensions between a priori logical knowledge and computational feasibility
Advanced foundational work on automata and recognizable sets