points by gbacon 2 days ago | 0 comments
The class NP-complete contains the hardest problems in NP. If you pick any problem in NP-complete, all problems in NP can be reduced to it (meaning that a solution to the problem you chose can be used to solve everything in the rest of NP) in polynomial time or “efficiently.” This applies to all of NP, including every other NP-complete problem, so in a sense, NP-complete problems are the same problem dressed in different clothing.
So the reduction to 3SAT could happen in principle, but it isn’t a necessary step.
Aún no hay comentarios.