8 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
  • 565

Only top scored, non community-wiki answers of a minimum length are eligible