0
$\begingroup$

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?

$\endgroup$
2
  • 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, 2019 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$ Jan 13, 2019 at 13:45

0

Your Answer

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

Browse other questions tagged or ask your own question.