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]

Limitations

[edit]
The graph shows time of solution of problem in milliseconds (ms) vs. problem size n for knapsack problems solved by a state-of-the-art specialized algorithm using a 933 MHz Pentium III computer (average of 100 instances, data from Pisinger[8]). The fit of the quadratic equation suggests that empirical algorithmic complexity for instances with 50–10,000 variables is O((log n)2) despite having exponential worst-case complexity estimate in theory.

While Cobham's thesis is an important milestone in the development of the theory of computational complexity, it has limitations as applied to practical feasibility of algorithms. The thesis essentially states that "P" means "easy, fast, and practical", while "not in P" means "hard, slow, and impractical". But this is not always true, because the thesis abstracts away some important variables that influence the runtime in practice:

  • It ignores constant factors and lower-order terms.
  • It ignores the size of the exponent. The time hierarchy theorem proves the existence of problems in P requiring arbitrarily large exponents.
  • It ignores the typical size of the input.

All three are related and are general complaints about analysis of algorithms, but they particularly apply to Cobham's thesis, since it makes an explicit claim about practicality. Under Cobham's thesis, a problem for which the best algorithm takes n200 instructions is considered feasible, and a problem with an algorithm that takes 20.00001 n instructions infeasible—even though one could never solve an instance of size n = 2 with the former algorithm, whereas an instance of the latter problem of size n = 106 could be solved without difficulty. In fields where practical problems have millions of variables (such as operations research or electronic design automation), even O(n3) algorithms are often impractical.[9]

A separate consideration is that in many cases, one is often content with approximate solutions if an exact solution cannot be found. For example, the travelling salesman problem is widely suspected to be unsolvable exactly in polynomial time (it is NP-hard), but good solutions can be obtained in polynomial time with methods such as the Christofides algorithm.

References

[edit]
  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]).
  8. ^ D. Pisinger, 2003. "Where are the hard knapsack problems?" Technical Report 2003/08, Department of Computer Science, University of Copenhagen, Copenhagen, Denmark, see [1] (Archived 2015-11-23 at the Wayback Machine), accessed 31 January 2015.
  9. ^ Rotman, Brian (18 June 2003). "Will the digital computer transform classical mathematics?". Phil. Trans. R. Soc. Lond. A. 361 (1809): 1675–1690. Bibcode:2003RSPTA.361.1675R. doi:10.1098/rsta.2003.1230. PMID 12952680. S2CID 38600389.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Cobham%27s_thesis&oldid=1186025488"