3 ms·
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 w
by 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.