In wikipedia, Cobham's thesis (or Cobham-Edmonds thesis) states:

computational problems can be feasibly computed on some computational device only if they can be computed in polynomial time

So according to my understanding, Cobham says that all problems that are in class $P$, then there exists a physical device that can solve this problem in short time (or a physical device that people can see the answer in their life-time).

Oded Goldreich's textbook of Computational Complexity states:

Cobham-Edmonds Thesis asserts that the time complexities in any two reasonable and general models of computation are polynomially related.That is, a problem has time complexity t in some reasonable and general model of computation if and only if it has time complexity poly(t) in the model of single-tape Turing machine.

It seems that Goldreich's definition of Cobham's thesis is that all model of computation that solve problems in complexity class P are polynomially related. I don't see any different from Goldreich's definition and the Extended Church-Turing Thesis which the later is not credited to any paper or person as far as I know.

Now can you clarify which definition is true for Cobhams' thesis, Is it by wikipedia definition or by Goldreich's definition? If you don't see any contradiction, then can you explain how these two definitions are related.


1 Answer 1


Cobham's thesis is essentially the Extended Church-Turing thesis. Historians of computer science have gone back and figured out who first proposed it, and attached his name to it.

What Cobham was actually talking about in his paper "The Intrinsic Computational Difficulty of Functions" [Proc. 1964 Congress for Logic, Methodology, and the Philosophy of Science, pp. 24-30, 1964, North-Holland] was how many computational steps it takes to compute a function, not to recognize a language, so he was talking about what we would today call FP and not P. What Cobham actually said in his paper is:

if we formalize the above definition [of FP] relative to various classes of computing machines we seem to always end up with the same well-defined class of functions.

He never mentions physical device, and I suspect that he was not thinking about physical devices, but about mathematical models of computation.

Thus, the thesis that Cobham actually proposed is that the class of functions FP is independent of the machine it is defined on (with the unwritten addendum that this machine is sufficiently powerful). This is quite closely related to Oded Goldreich's definition, and much farther from the Wikipedia definition.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.