| ▲ | Good4boothee 5 hours ago | |
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. | ||