Cobham's Thesis - Objections

Objections

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. To begin with, it 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, we are to call a problem for which the best algorithm takes 10100n instructions feasible, and a problem with an algorithm that takes 20.00001 n infeasible—even though we could never solve an instance of size n=1 with the former algorithm, whereas we could solve an instance of the latter problem of size n=106 without difficulty. As we saw, it takes a day on a typical modern machine to process 2n 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 2n-time algorithm feasible in practice on the inputs we have. Conversely, in fields where practical problems have millions of variables (such as Operations Research or Electronic Design Automation), even O(n3) algorithms are often impractical.

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.