Cobham's Thesis on Feasibility of the Class P
Mathematics Accomplishment | 1965
IBM researcher: Alan Cobham
Where the work was done: IBM T.J. Watson Research Center
What we accomplished: One of the first, if not the first mentions of the class P.
Related links: From Wikipedia, "Cobham's thesis, also known as Cobham–Edmonds thesis (named after Alan Cobham and Jack Edmonds),asserts that computational problems can be feasibly computed on some computational device only if they can be computed in polynomial time; that is, if they lie in the complexity class P."
- Alan Cobham (1965), The intrinsic computational difficulty of functions, Proceedings of Logic, Methodology, and Philosophy of Science II, North Holland
- This paper also mentions the class NP, though Cobham called P L and NP L+
Image credit: Jeffrey Shallit