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

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 NPcomplete 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