Cobham's thesis

Not to be confused with Cobham's theorem.

Cobham's thesis, also known as Cobham–Edmonds thesis (named after Alan Cobham and Jack Edmonds),[1][2][3] 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.[4] In modern terms, it identifies tractable problems with the complexity class P.

Formally, to say that a problem can be solved in polynomial time is to say that there exists an algorithm that, given an n-bit instance of the problem as input, can produce a solution in time O(nc), using the big-O notation and with c being a constant that depends on the problem but not the particular instance of the problem.

Alan Cobham's 1965 paper entitled "The intrinsic computational difficulty of functions"[5] is one of the earliest mentions of the concept of the complexity class P, consisting of problems decidable in polynomial time. Cobham theorized that this complexity class was a good way to describe the set of feasibly computable problems.

Jack Edmonds's 1965 paper "Paths, trees, and flowers"[6] is also credited with identifying P with tractable problems.[7]

  1. ^ Oded Goldreich (2008), Computational complexity: a conceptual perspective, Cambridge University Press, p. 128, ISBN 978-0-521-88473-0.
  2. ^ Dexter Kozen (2006), Theory of computation, Birkhäuser, p. 4, ISBN 978-1-84628-297-3.
  3. ^ Egon Börger (1989), Computability, complexity, logic, Elsevier, p. 225, ISBN 978-0-444-87406-1.
  4. ^ Homer, Steven; Selman, Alan L. (1992), "Complexity Theory", in Kent, Alan; Williams, James G. (eds.), Encyclopedia of Computer Science and Technology, vol. 26, CRC Press.
  5. ^ Alan Cobham (1965), The intrinsic computational difficulty of functions (PDF).
  6. ^ Edmonds, Jack (1965). "Paths, trees, and flowers". Can. J. Math. 17: 449–467. doi:10.4153/CJM-1965-045-4. S2CID 18909734.
  7. ^ Meurant, Gerard (2014). Algorithms and Complexity. Elsevier. p. p. 4. ISBN 978-0-08093391-7. A problem is said to be feasible if it can be solved in polynomial time (as stated for the first time in Edmonds [26] [1965, Paths, trees, and flowers]).