alt Hacker NewsI’m pretty sure “counterexample” is the wrong word here.
Replies
js8 • today at 3:19 PM
Why? A counterexample to P!=NP would be a polynomial algorithm for SAT. If it exists, it might be a constructible object.
➕ show 1 reply
I’m pretty sure “counterexample” is the wrong word here.
Why? A counterexample to P!=NP would be a polynomial algorithm for SAT. If it exists, it might be a constructible object.
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?