Cobham's thesis
From Wikipedia, the free encyclopedia
Cobham's thesis asserts that computational problems can be feasibly computed on some computational device only if they can be computed in polynomial time.
Alan Cobham's 1965 paper entitled “The intrinsic computational difficulty of functions” is one of the earliest mentions of the concept of the complexity class P, or problems recognizable in polynomial amount of 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.
[edit] See also
[edit] References
A. Cobham. The intrinsic computational difficulty of functions. In Proc. Logic, Methodology, and Philosophy of Science II, North Holland, 1965.
