It’s not clear to me what the slogan is intended to mean, and the example only confuses me further. In the first paragraph of the OP, “generate” appears to mean “find a solution to a given problem”. In the supposed counterexample, it means “find a problem that has a given solution”. These are very different things. The former task is hard for problems in NP–P, the latter task is typically trivial.
“Does this program compute this function?” is a hard problem — unsolvable.
“Is this a proof that this program computes this function?” is an easy problem — primitive recursive in any reasonable encoding scheme, maybe of near-linear complexity.
Both of these might be described as “verification”.
It’s not clear to me what the slogan is intended to mean, and the example only confuses me further. In the first paragraph of the OP, “generate” appears to mean “find a solution to a given problem”. In the supposed counterexample, it means “find a problem that has a given solution”. These are very different things. The former task is hard for problems in NP–P, the latter task is typically trivial.
“Verification” is also vague.
“Does this program compute this function?” is a hard problem — unsolvable.
“Is this a proof that this program computes this function?” is an easy problem — primitive recursive in any reasonable encoding scheme, maybe of near-linear complexity.
Both of these might be described as “verification”.