In the following paper:

Alan Cobham (1965), "The intrinsic computational difficulty of functions", Proc. Logic, Methodology, and Philosophy of Science II, North Holland.

Cobham defined the class P as the class for efficient computations. He stated that his notion is machine-independent.

Unfortunately, I don't have access to this paper. Can anyone clarify the points he made there? Is it just a thesis, or something proved?

  • 5
    $\begingroup$ AFAIK, he defined the class $P$ as the smallest set of functions containing some simple initial functions, closed under composition, and bounded recursion on notation. It is machine independent in the sense that it is a logical characterization similar to the definition of primitive recursive functions, it does not mention any machines. $\endgroup$
    – Kaveh
    Commented Sep 29, 2010 at 18:50

1 Answer 1


You can try to look at the paper A new recursion-theoretic characterization of the polytime functions by Stephen Bellantoni and Stephen Cook, which has very nice discussion on Cobham's polynomial-time characterization in the introduction section. This paper also has pointers to other related works. You can easily find the paper somewhere on the web in case you are not subscribed to Springer.


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.