I’m afraid that this take is incredibly confused, so much that it’s hard to know where to start with correcting it.
Maybe the most consequential error is the misunderstanding of what “verify” means in this context. It means “checking a proof of a solution” (which in the case of a decision problem in NP would be a proof of a “yes” answer). In a non-mathematical context, you can loosely think of “proof” as consisting of reasoning, citations, etc.
That’s what went wrong with the halting problem example. The generator did not support their claim that the program halts. If they respond to this complaint by giving us a proof that’s too hard, we can (somewhat tautologically) ensure that our verifier job is easy by sending back any program+proof pair where the proof was too hard to verify.
I’m afraid that this take is incredibly confused, so much that it’s hard to know where to start with correcting it.
Maybe the most consequential error is the misunderstanding of what “verify” means in this context. It means “checking a proof of a solution” (which in the case of a decision problem in NP would be a proof of a “yes” answer). In a non-mathematical context, you can loosely think of “proof” as consisting of reasoning, citations, etc.
That’s what went wrong with the halting problem example. The generator did not support their claim that the program halts. If they respond to this complaint by giving us a proof that’s too hard, we can (somewhat tautologically) ensure that our verifier job is easy by sending back any program+proof pair where the proof was too hard to verify.