6
$\begingroup$

I was wondering why 3-SAT is often chosen as the candidate problem from which one reduces from to prove the NP-completeness of another algorithm. I've seen it justified in places such as K&T by

We now show that 3-SAT $\leq_p$ Hamiltonian Cycle. Why are we reducing from 3-SAT? Essentially, faced with Hamiltonian Cycle, we really have no idea what to reduce from; it’s sufficiently different from all the problems we’ve seen so far that there’s no real basis for choosing. In such a situation, one strategy is to go back to 3-SAT, since its combinatorial structure is very basic.

(I believe also that the Super Mario NP-completeness proof uses a reduction from 3-SAT.)

However, even they admit that

Of course, this strategy guarantees at least a certain level of complexity in the reduction, since we need to encode variables and clauses in the language of graphs.

I've seen that certain cases lend themselves to reducing from other problems with simpler variables and constraints (e.g. from Hamiltonian cycle). So I'm wondering why 3-SAT is often chosen/taught as a default, given that constructing variable and clause gadgets and encoding non-conflicting constraints is not necessarily straightforward.

EDIT: The plot thickens! Here's what mathematician Robert Kleinberg has to say:

enter image description here

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ It's not necessarily straightforward, but it's often more straightforward than it is for many other NP-complete problems that could be reduced to. You might want to have a look at en.wikipedia.org/wiki/Games,_Puzzles,_and_Computation — while it covers more than just NP-completeness, the framework that it presents IMHO does a good job of explaining why SAT is such a useful baseline. $\endgroup$
    – Steven Stadnicki
    Commented Apr 2 at 5:45
  • $\begingroup$ I think once you prove Hamiltonian cycle (and from there, many other graph algorithms) those also become fairly frequent reduction targets, right? Graph coloring or cliques in particular, iirc. Though certainly you can choose many for any particular problem you're building a reduction for. $\endgroup$
    – Kaia
    Commented Apr 2 at 20:01
  • $\begingroup$ Yeah, it seems like the best way to go is to default to problems with similar structure rather than to default to 3-SAT. As codeR pointed out, it might be for historical reasons and as a source of good practice in designing gadgets. $\endgroup$
    – entangled_photon
    Commented Apr 2 at 20:59

1 Answer 1

Reset to default
9
$\begingroup$

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 Cook–Levin theorem). Secondly, it is a good practice exercise to build reduction gadgets for 3-SAT, which often reveal some structural properties. These properties may be exploited to devise efficient algorithms. Lastly, there are many good SAT solvers available these days. By designing a similar kind of reduction in the opposite direction (to SAT), we may use a SAT solver to solve an original problem instance (possibly small ones) to acquire some insight.

Also, you may refer to this discussion as well.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Yes you are right, I have rectified my mistake. :) $\endgroup$
    – codeR
    Commented Apr 2 at 8:53
  • $\begingroup$ This is a good answer! Can you give an example of how such a reduction can "reveal...structural properties"? For instance, in the (canonical) 3-SAT $\leq_p$ Independent Set, we encode conflicts verbatim with how Independent Set does, namely, edges between negated terms and edges between terms in a clause, and I don't believe this reveals much as to the structure of IS. $\endgroup$
    – entangled_photon
    Commented Apr 2 at 19:31
  • 1
    $\begingroup$ One that immediately comes to mind is that in graph coloring, the main hurdle is the presence of one or more cycles. Also, sometimes the presence of a clique may make your life easier by forcing your hand and thus reducing the possible choices. FPT algorithms often exploit these to get solutions faster in most practical cases. A reduction gadget typically use these structural properties to enforce constraits. $\endgroup$
    – codeR
    Commented Apr 4 at 9:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.