4 ms·

You have misunderstood the article. The question being discussed was not "How hard is it to solve P?=NP", it was "Is P?=NP itself NP-hard", which is just an inv

You have misunderstood the article. The question being discussed was not "How hard is it to solve P?=NP", it was "Is P?=NP itself NP-hard", which is just an invalid question.

landc 2y ago
Sounds like the same question to me, for sure the students intended it that way. Many hard problems feel like you need an internal mental SAT solver to arrive at the solution. Anyway, even if it were an invalid question, his answer still does not make any sense.
- jonathrg 2y ago
  Those are definitely not the same question, NP-hardness has a precise meaning while "hard to solve" is a subjective judgement The answer is trying to show the absurdity of the question. It's like asking for the time complexity of factoring 120. If there is no input to the algorithm, the answer is always trivial.
mistercow 2y ago
Nitpicking, but I’d say that it’s a valid question with a trivial answer. A problem is just a set of question/answer pairs. “P?=NP” is just a decision problem with a single instance, and all decision problems with finite instances are decidable in constant time. Consider this rephrasing of the question: “Let X be an NP-complete problem. Can X be solved in polynomial time?” This is a problem with an infinite number of instances, all of which reduce to “P?=NP”, so we know that this problem can be decided in constant time.
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.

You have misunderstood the article. The question being discussed was not "How hard is it to solve P?=NP", it was "Is P?=NP itself NP-hard", which is just an invalid question.

landc 2y ago

Sounds like the same question to me, for sure the students intended it that way. Many hard problems feel like you need an internal mental SAT solver to arrive at the solution. Anyway, even if it were an invalid question, his answer still does not make any sense.

jonathrg 2y ago
Those are definitely not the same question, NP-hardness has a precise meaning while "hard to solve" is a subjective judgement The answer is trying to show the absurdity of the question. It's like asking for the time complexity of factoring 120. If there is no input to the algorithm, the answer is always trivial.

mistercow 2y ago

Nitpicking, but I’d say that it’s a valid question with a trivial answer. A problem is just a set of question/answer pairs. “P?=NP” is just a decision problem with a single instance, and all decision problems with finite instances are decidable in constant time. Consider this rephrasing of the question: “Let X be an NP-complete problem. Can X be solved in polynomial time?” This is a problem with an infinite number of instances, all of which reduce to “P?=NP”, so we know that this problem can be decided in constant time.

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.