Does anyone know of an accessible introduction to Cobham's model independent characterization of FP and it's equivalence to the standard definition using Turing machines? The best source I could find on-line was https://www.cs.toronto.edu/~sacook/homepage/ptime.pdf : a paper by Stephen Bellantoni and Stephen Cook detailing another similar approach. However, it is a little too difficult for me to understand.

As a side question, does anyone know if researchers are still interested in Cobham's formulation or feel it could possibly lead to resolving open problems?

  • $\begingroup$ I'm not sure how accessible you expect a recursion-theoretic characterization of polynomial time to be. Such things are necessarily very technical and they're difficult to understand because they involve difficult concepts. $\endgroup$ Jun 25 '15 at 20:57
  • 1
    $\begingroup$ @DavidRicherby I'm mainly interested in just the basic functions it entails because I know at least that FP is the class closed under certain operations and functions (one I think is called the "smash" function, but I don't know its formal definition). I guess the equivalence proof will be beyond my reach at this point. $\endgroup$
    – Ari
    Jun 25 '15 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.