I’m pretty sure “counterexample” is the wrong word here.

Good4boothee 5 hours ago | parent | next [-]

Isn't it a bit Catch 22 anyway? If someone finds a algorithm to reduce some NP task X to class P, then that just means X wasn't a true NP task and P!=NP is still undecided?

	▲	layer8 5 hours ago \| parent \| next [-]
		If it’s an NP-complete [0] problem like SAT, as many NP problems are, then we are done, because all NP problems can be reduced to it (in polynomial time). [0] https://en.wikipedia.org/wiki/P_versus_NP_problem#NP-complet...
	▲	Tyr42 5 hours ago \| parent \| prev \| next [-]
		You can prove something is in NP by providing a (polynomial) reduction from a known NP hard task, and vice versa. All the known NP problems (Knapsack, SAT, etc) are mutually reducable in this way, so solving one lets you solve the others. So if X was shown to be NP, then given a polynomial time solution to X, you can stack the polynomial time reduction from X to SAT to solve SAT in polynomial time too.
	▲	SetTheorist 5 hours ago \| parent \| prev [-]
		AIUI if you have an (polynomial-time) algorithm to reduce some NP-complete task to P then you have indeed shown that P=NP.

▲

js8 5 hours ago | parent | prev [-]

Why? A counterexample to P!=NP would be a polynomial algorithm for SAT. If it exists, it might be a constructible object.

▲

layer8 4 hours ago | parent [-]

That’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.

	▲	js8 3 hours ago \| parent [-]
		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.