3 ms·
The exact wording (as of now, I do not know if he edits) is: "Could the P versus NP question itself be NP-hard, and therefore impossible to solve?" That clearl
by alfdsv 2y ago
The exact wording (as of now, I do not know if he edits) is: "Could the P versus NP question itself be NP-hard, and therefore impossible to solve?"
That clearly implies solving. Aaronson is pretty sloppy with his own definitions and yet criticizes his students.
An unambiguous presentation would be:
1) Contrary to usual language use, we define "answer P?=NP" as "print 'yes' or 'no' or 'undecidable'".
2) By "program" we do not mean a single program, but three separate programs that print "yes", "no", or "undecidable".
3) We claim the existence of the program, not that it will ever be possible to know which of the three programs is correct.
- School-Cotton 2y ago> By "program" we do not mean a single program, but three separate programs that print "yes", "no", or "undecidable". You can think of it not as he is describing three separate programs, but giving three separate possible descriptions of one program and asserting that one of them is indeed the correct description.