Does there exist a primitive recursive algorithm whose execution result on arbitrary input can be verified without re-executing the algorithm itself, or with a computational complexity that is lower than the recursive algorithm?

  • 3
    $\begingroup$ Would a very bad algorithm for an easy problem be an example of what you're looking for? $\endgroup$ – Ben Barber Jan 12 at 17:31
  • $\begingroup$ Isn't the typical NP-complete problem an instance of this? You can solve it in exponential time, say, but verify it in polynomial time. $\endgroup$ – Joel David Hamkins Jan 13 at 13:45

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.