Comment

Comment by gbacon

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.

parent gbacon 14 days ago

No comments yet

Be the first to share your thoughts.

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton