logoalt Hacker News

js8today at 3:19 PM1 replyview on HN

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


Replies

layer8today at 3:32 PM

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.

show 1 reply