3 ms·
No, NP Completeness states that you can go either way. Specifically: A problem X is NP Complete if: 1: X is in NP. 2: Every problem in P can be reduced to X
by devinj 16y ago
No, NP Completeness states that you can go either way.
Specifically: A problem X is NP Complete if:
1: X is in NP.
2: Every problem in P can be reduced to X in polynomial time.
We have established the first condition by intuition-- pathfinding is easy.
Immediately, we know, then, that there exists some way to reduce this to 3-SAT, in a way general for any level.
Reducing 3-SAT to this, however, proves the second criterion (because 3-SAT is NP-complete, so by doing two reductions you can reduce any NP problem to this, in time at worst the cost of doing sum of the two polynomials describing the complexity of the reductions).
So we can also convert 3-SAT-- or any NP-complete problem, in fact, and even more generally, any NP problem-- to this in poly-time.
- Chirono 16y agoIndeed. You're correct. But this does show NP-completeness. A rather incredible theorem is the Cook-Levin theorem which states that any problem that can be verified in polynomial time can reduced to an instance of sat SAT (in polynomial time). The practical upshot of this is that to show NP-completeness, you only need to provide a polynomial certificate and reduction to SAT, or some other know NP complete problem.
- devinj 16y agoI didn't say otherwise, and did explain why reducing 3-SAT to this proved NP-completeness.