alt Hacker NewsThat’s not a counterexample to P != NP, it’s a proof that P = NP. You can’t prove that two sets are the same by counterexample. What you could do is disprove P = NP by counterexample, by showing that some problem is in NP but not in P.
At best, a polynomial algorithm for SAT would be a counterexample to the claim that no NP-complete problem is in P.
Sorry, it seems like nitpicking to me. You haven't shown my usage of the word counterexample is wrong, at all.
I think a proven counterexample to Q is always a proof of not Q.
> You can’t prove that two sets are the same by counterexample.
You can in this case.
> What you could do is disprove P = NP by counterexample, by showing that some problem is in NP but not in P.
You could argue that counterexample is defined in one direction only, by convention, as to which hypothesis is more believed. In that case, my usage would be more valid, because the general consensus is P!=NP.
You could also argue that a counterexample should be some finite, constructible object. But that's actually also in favor of my usage - a difficult class is an infinite set, while an algorithm has a finite description.
Also note that AI can still find the counterexample (the actual algorithm), without proving it is a counterexample. Again, my usage of the word counterexample favors that definition of what counterexample is.
But honestly I think it would be more productive to spend this effort on thinking about actual counterexample to P!=NP.