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?
$\begingroup$
$\endgroup$
2
-
3$\begingroup$ Would a very bad algorithm for an easy problem be an example of what you're looking for? $\endgroup$– Ben BarberJan 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$– Joel David HamkinsJan 13, 2019 at 13:45
Add a comment
|