Welcome to the MedLibrary.org Wikipedia Supplement on Cobham's thesis -- Please Click to Return to Front Page

Cobham's thesis asserts that computational problems can be feasibly computed on some computational device only if they can be computed in polynomial time.^[1]

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(n^c), where c is 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"^[2] 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. Any problem that cannot be contained in P is not feasible, but if a real-world problem can be solved by an algorithm existing in P, generally such an algorithm will eventually be discovered.

The class P is a useful object of study because it is not sensitive to the details of the model of computation: for example, a change from a single-tape Turing machine to a multi-tape machine can lead to a quadratic speedup, but any algorithm that runs in polynomial time under one model also does so on the other.

Reasons behind Cobham's Thesis

The thesis is widely considered to be a good rule of thumb for real-life problems. Typical input lengths that users and programmers are interested in are between 100 and 1,000,000, approximately. Consider an input length of n=100 and a polynomial algorithm whose running time is n². This is a typical running time for a polynomial algorithm. (See the "Objections" section for a discussion of atypical running times.) The number of steps that it will require, for n=100, is 100²=10000. A typical CPU will be able to do 10⁹ operations per second. So this algorithm will finish in (10000 ÷10⁹) = .00001 seconds. A running time of .00001 seconds is reasonable, and that's why this is called a practical algorithm. The same algorithm with an input length of 1,000,000 will take about 17 minutes, which is also a reasonable time.

Meanwhile, an algorithm that runs in exponential time might have a running time of 2ⁿ. The number of operations that it will require, for n=100, is 2¹⁰⁰. It will take (2¹⁰⁰ ÷ 10⁹) ≈ 1.3×10²¹ seconds, which is (1.3×10²¹ ÷ 31556926) ≈ 4.1×10¹³ years. The largest problem this algorithm could solve in a day would have n=46, which seems very small.

Objections

This section may contain original research or unverified claims. Please help Wikipedia by adding references. See the talk page for details.(May 2008)

There are many lines of objection to Cobham's thesis. 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, for the following reasons:

• It ignores constant factors and lower-order terms.
• It ignores the size of the exponent.
• 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, we are to call a problem for which the best algorithm takes 10¹⁰⁰n instructions feasible, and a problem with an algorithm that takes 2^{0.00001 n} infeasible—even though we could never solve an instance of size n=1 with the former algorithm, whereas we could solve instance of the latter problem that have size n=10⁶ without difficulty. As we saw, it takes a day on a typical modern machine to process 2ⁿ operations when n=46; this may be the size of inputs we have, and the amount of time we have to solve a typical problem, making the 2ⁿ-time algorithm feasible in practice on the inputs we have.

The typical response to this objection is that in general, algorithms for computational problems that naturally occur in computer science and in other fields have neither enormous nor minuscule constants and exponents. Even when a polynomial-time algorithm has a large exponent, historically, other algorithms are subsequently developed that improve the exponent. Also, typically, when computers are finally able to solve problems of size n fast enough, users of computers ask them to solve problems of size n+1. These are all subjective statements.

Another objection is that Cobham's thesis only considers the worst-case inputs. Some NP-hard problems can be solved quite effectively on many of the large inputs that appear in practice; in particular, the Travelling Salesman Problem and Satisfiability can often be solved exactly even with input sizes in the tens or hundreds of thousands. Even though the same algorithms can be made to fail (take too long, use too much memory, or trigger an error condition) on some inputs, users may be content with only sometimes getting solutions. In some cases, in fact, an algorithm that might require exponential time is the technique of choice because it only does so on highly contrived examples; the simplex method is one such example.

Cobham's thesis also ignores other models of computation. A problem that requires taking exponential time to find the exact solution might allow for a fast approximation algorithm that returns a solution that is almost correct. Allowing the algorithm to make random choices, or to sometimes make mistakes, might allow an algorithm to run in polynomial time rather than exponential time. Though this is currently believed to be unlikely (see RP, BPP), in practice, randomized algorithms are often the fastest algorithms available for a problem (quicksort, for example, or the Miller–Rabin primality test). Finally, quantum computers are able to solve in polynomial time some problems that have no known polynomial time algorithm on current computers, such as Shor's algorithm for integer factorization, but this is not currently a practical concern since large-scale quantum computers are not yet available.

References

• Steven Homer and Alan L. Selman (1992). "Complexity Theory", in Alan Kent and James G. Williams: Encyclopedia of Computer Science and Technology 26. CRC Press.
• Alan Cobham (1965). "The intrinsic computational difficulty of functions", Proc. Logic, Methodology, and Philosophy of Science II. North Holland.
• Lloyd, Seth. "Computational capacity of the universe". Accessed March 31, 2008.

Wikipedia content modification information:

• This page was last modified on 3 October 2008, at 00:12.

Wikipedia Authorship and Review

Wikipedia content provided here is not reviewed directly by MedLibrary.org. Wikipedia content is authored by an open community of volunteers and is not produced by or in any way affiliated with MedLibrary.org.

Wikipedia Usage Guidelines

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article on "Cobham's thesis".

The URL for this specific entry is:

• http://medlibrary.org/medwiki/Cobham's_thesis

All Wikipedia text is available under the terms of the GNU Free Documentation License. (See Copyrights for details). Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc.