Cobham's thesis

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] 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.

In fields where practical problems have millions of variables (such as operations research or electronic design automation), even O(n3) algorithms are often impractical.

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.