The most trivial programs that halt are also trivially verifiable as halting, though. Yes, you can’t have a fully general verification algorithm, but e.g. “does the program contain zero loops or recursive calls” covers the most trivial programs (for my definition of “trivial”, anyway). I think this example of yours fails to capture the essence—which I think is supposed to be “someone easily spewing out lots of incomprehensible solutions to a problem”.
In fact, more generally, if there is a trivial algorithm to generate solutions, then this immediately maps to an algorithm for verifying trivial solutions: run the trivial algorithm for a reasonable number of steps (a number such that the generation would no longer be called “trivial” if it took that long) and see if the proposed solution appears among them. The hardest part is knowing what that algorithm was—but by assumption the algorithm was trivial, which puts some limits on how hard finding it can be.[1]
The main path that might still qualify as “trivially generating lots of solutions that are hard to verify by someone who has some notion of how the generation works” is if the generation process includes randomness. E.g. make a comprehensible program, then insert a bunch of trash and permute things around. Or, say, have a number maze and the question is “Is there a path through these numbers such that sha256(those numbers) = 0xabcde?”—and the person who made the maze did so by picking random numbers, computing their sha256, putting them into a maze, and filling the rest of the maze with more random numbers. I probably would have recommended that example.[2]
This brings it back to NP, incidentally: if the generation process was trivial, then it must have taken a “reasonable” amount of time; and if it used N bits of randomness, then a verifier has 2^N possibilities to try, and if it guesses right the first time (a nondeterministic machine) then it terminates quickly. But this time the verification process is NP, while the generation process is P.
Though if we concern ourselves with not “trivial” algorithms but rather “algorithms that aren’t too complicated”—which might be approximated by “algorithms specified in under N characters”—then there are exponentially many algorithms to sort through.
Or, a version that meets more rigorous constraints: The predicate is, “Is this an n x k grid of bytes such that there is a nonrepeating path through the grid, such that sha256(those bytes), xored with the top row of bytes, yields zero?” The generation algorithm is to pick random bytes, sha256 them, draw a random path in a grid and put them there, fill out the rest of the grid with random bytes, and put the sha256 result as the top row of bytes.
The most trivial programs that halt are also trivially verifiable as halting, though. Yes, you can’t have a fully general verification algorithm, but e.g. “does the program contain zero loops or recursive calls” covers the most trivial programs (for my definition of “trivial”, anyway). I think this example of yours fails to capture the essence—which I think is supposed to be “someone easily spewing out lots of incomprehensible solutions to a problem”.
In fact, more generally, if there is a trivial algorithm to generate solutions, then this immediately maps to an algorithm for verifying trivial solutions: run the trivial algorithm for a reasonable number of steps (a number such that the generation would no longer be called “trivial” if it took that long) and see if the proposed solution appears among them. The hardest part is knowing what that algorithm was—but by assumption the algorithm was trivial, which puts some limits on how hard finding it can be.[1]
The main path that might still qualify as “trivially generating lots of solutions that are hard to verify by someone who has some notion of how the generation works” is if the generation process includes randomness. E.g. make a comprehensible program, then insert a bunch of trash and permute things around. Or, say, have a number maze and the question is “Is there a path through these numbers such that sha256(those numbers) = 0xabcde?”—and the person who made the maze did so by picking random numbers, computing their sha256, putting them into a maze, and filling the rest of the maze with more random numbers. I probably would have recommended that example.[2]
This brings it back to NP, incidentally: if the generation process was trivial, then it must have taken a “reasonable” amount of time; and if it used N bits of randomness, then a verifier has 2^N possibilities to try, and if it guesses right the first time (a nondeterministic machine) then it terminates quickly. But this time the verification process is NP, while the generation process is P.
Though if we concern ourselves with not “trivial” algorithms but rather “algorithms that aren’t too complicated”—which might be approximated by “algorithms specified in under N characters”—then there are exponentially many algorithms to sort through.
Or, a version that meets more rigorous constraints: The predicate is, “Is this an n x k grid of bytes such that there is a nonrepeating path through the grid, such that sha256(those bytes), xored with the top row of bytes, yields zero?” The generation algorithm is to pick random bytes, sha256 them, draw a random path in a grid and put them there, fill out the rest of the grid with random bytes, and put the sha256 result as the top row of bytes.