Extremely strange reasoning from Aaronson. He goes from the question "How hard is it to solve P?=NP" to a vague existence claim of a program that cannot be concretely written, unless it takes "P==NP" and "P!=NP" as inputs, which would be a tautology.
This claimed program does not answer the above question at all. His students are correct, he is wrong.
> vague existence claim of a program that cannot be concretely written
It can be concretely written. It's either "return True" or "return False". As of today we don't know which one of the two is this. However our lack of knowledge is not relevant to the question if it's computable or not. Definition of computability doesn't rely on it.
> unless it takes "P==NP" and "P!=NP" as inputs, which would be a tautology.
It doesn't take any inputs at all since none are necessary. It's a constant function. The question of computability isn't relevant for constant functions or for functions with a finite set of possible inputs -- they are computable as switch-case on all possible inputs.
The problem only appears with functions that have an infinite set of possible inputs where the switch-case approach won't work. You need an _algorithm_ to convert inputs to outputs and sometimes this algorithm just can't exists, regardless of how far we've got in proving truthfulness of various mathematical statements.
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.
> 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.
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.
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.
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.
This claimed program does not answer the above question at all. His students are correct, he is wrong.