Skip to main content

New answers tagged

9 votes

Why is 3-SAT used for proving NP-Completeness so often?

You can indeed use any known NP-Hard problem as a candidate for your reduction. In my opinion, it has more to do with the fact that 3-SAT (a variant of SAT) was originally proven to be NP-Hard (see ...
codeR's user avatar
  • 706

Top 50 recent answers are included