5 ms·
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 stil
by Good4boothee 2mo 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?
- SetTheorist 2mo agoAIUI if you have an (polynomial-time) algorithm to reduce some NP-complete task to P then you have indeed shown that P=NP.
- Tyr42 2mo agoYou 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.
- layer8 2mo agoIf 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-completeness https://en.wikipedia.org/wiki/P_versus_NP_problem#NP-complet...
- subsistence234 2mo agoNP doesn't mean "we don't know a polynomial time algorithm for it", it means "a proposed answer can be verified as correct in polynomial time"