# 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

BACK TO IBM RESEARCH ACCOMPLISHMENTS