How do I know that I generated a program that halts?
a) I can prove to myself that my program halts ⇒ the solution consists of both the program and the proof ⇒ the verification problem is a sub-problem of the generation problem.
b) I followed a trusted process that is guaranteed to produce valid solutions ⇒ the solution consists of both the program and the history that generated the proof of the process ⇒ if the history is not shared between the 2 problems, then you redefined “verification problem” to include generation of all of the necessary history, and that seems to me like a particularly useless point of view (for the discussion of P vs NP, not useless in general).
In the latter point of view, you could say:
Predicate: given a set of numbers, is the first the sum of the latter 2?
Generation problem: provide an example true solution: “30 and prime factors of 221”
Verification problem: verify that 30 is the sum of prime factors of 221
WTF does that have to say about P vs NP? ¯\_(ツ)_/¯
TypeError: Comparing different “solutions”.
How do I know that I generated a program that halts?
a) I can prove to myself that my program halts ⇒ the solution consists of both the program and the proof ⇒ the verification problem is a sub-problem of the generation problem.
b) I followed a trusted process that is guaranteed to produce valid solutions ⇒ the solution consists of both the program and the history that generated the proof of the process ⇒ if the history is not shared between the 2 problems, then you redefined “verification problem” to include generation of all of the necessary history, and that seems to me like a particularly useless point of view (for the discussion of P vs NP, not useless in general).
In the latter point of view, you could say:
WTF does that have to say about P vs NP? ¯\_(ツ)_/¯