Proof Hampath is NP-Complete

Question

I'm really confused by the proof that Hampath is NP-Complete. In order to prove something is NP-Complete, we can reduce another NP-Complete problem to it. So we want to take 3-SAT and reduce it to Hampath, that is, we want to simulate an input into 3-SAT and have 3-SAT accept iff there Hampath accepts. Or, in other words, we assume that we can solve Hampath in P time, then we can show that we can solve 3-SAT in P time as well, thus forming a contradiction. So I understand how it works, my questions are:

1. Why reduce to 3-SAT, why not just SAT?
2. I've read through the proof a few times, with gadgets and logical clauses, etc. And I just can't make any sense of it. I'm using Sipser's book, but I've also googled it. Does anyone have a good explanation and or resources to check out to make this clearer?

Thanks!

Answer 1

You're a bit confused about the terminology: in order to show that HAMPATH is NP-complete, you need to show that it's in NP (that's very easy) and that every problem in NP reduces to it. You do that by reducing some other NP-complete problem to HAMPATH.

As Theo noted, 3SAT is a special case of SAT, and so it's easier use 3SAT. The reduction that works for SAT will also work for 3SAT, but it may need to handle more cases. I'm not familiar with this particular reduction, but it might be that it's actually straightforward to generalize it to the "general case", but there's nothing to be gained by doing it.

Reductions showing a problem is NP-complete are usually like that - very intricate and slightly hard to follow. But usually there's the main idea - e.g., what corresponds to variables, what corresponds to clauses, why it should work - and the technical details. See first that you understand the main idea.

The technical details break into two parts. One part is the gadgets - you need to understand what the gadgets are supposed to do and how they accomplish it. The second part is proving that the construction works. In your case, it's probably easy to show that if the 3SAT instance is satisfiable, then the graph has a Hamiltonian path. It's probably more difficult to show that if the instance is unsatisfiable, the graph doesn't have any Hamiltonian paths. There's some intuition which leads us to believe that to be the case, but we still have to prove it, and the proof might be tricky.

Don't get discouraged if you don't "get it" right away. The best thing to understand these proofs is to do some of your own. Only then can you appreciate the thought processes behind such proofs. Better still, you might try working out a similar proof yourself, and see where you get stuck. There are some obstacles to overcome, and if you're aware of them then the construction will become much more interesting.

---

Looking at the reduction, I think Sisper explains it pretty well. In fact, for an expert it might be enough to mostly look at all the figures. The pattern of this reduction is very standard, so once you understand this one, you'll be in much better position to understand a whole lot of them!

The idea is to have variable-gadgets and clause-gadgets. The variable-gadgets can be traversed in two ways (according to the truth assignment). The clause-gadgets can be traversed-through from a satisfying literal.

So far for the idea. The construction itself is pretty simple, and it's easy to check that if a formula is satisfiable then there's a Hamiltonian path. It's also easy to see that if there's a similarly-looking Hamiltonian path then there's a satisfying assignment. The hard part is showing that all Hamiltonian paths "look as if they came out from a truth assignment", which must be satisfying.

Answer 2

For your first question, "Why reduce to 3-SAT, why not just SAT?", think about the direction of what is being solved using what.

If you want to show that HAMPATH is NP-Hard, you want to convert an instance of a known NP-Hard problem to HAMPATH. HAMPATH could solve all sorts of other problems too, but the reduction only deals with the subset of HAMPATH problems that correspond to the original. So HAMPATH is in some sense bigger than the original.

Assume that you know a reduction from 3-SAT to HAMPATH (via Sipser). Now consider SAT (and assume you know nothing else about it NP-wise). Since it is an obvious generalization of 3-SAT (doesn't have all those 3-SAT restrictions), it may include more instances than are solvable using HAMPATH. The more restricted 3-SAT is (obviously) easier than SAT so is more likely to have some kind of easy reduction to HAMPATH.

Part of the confusion may lie in that there is a reduction from SAT to 3-SAT. As just mentioned 3-SAT -obviously- reduces to SAT, but not the other way. And that's part of the clever problem solving that needs to happen sometimes; you may need to show that some restricted version of a tool can, with only a little more work (a polynomial or logspace amount of work) solve what -looks- like a harder problem.

Another view on 'why', is that sometimes being more narrow in specifications (like in 3-SAT) actually helps in the problem solving because you have fewer intellectual choices to make in the reduction. Since you -do- know that SAT is NP-Hard, you could somehow create arbitrary 'logical' graph gadgets to show reduction. But 3-SAT is useful for so many reductions because it is so constrained.

As to alternates, I can only suggest continuing your google search or looking through other texts (Papadimitriou, or CLRS come to mind)

Answer 3

As per Yuval's suggestion, I'm making my comment into an answer (but the proviso remains: I'm far from being an expert in complexity theory):

1. If you find a polynomial reduction of 3-SAT to Hampath, then you know that Hampath is NP-hard. That is, if you can solve Hampath, then you can solve every NP problem, since every NP problem can be polynomially reduced to 3-SAT by the Cook-Levin theorem. Note that we're not looking for a contradiction, here.

2. NP-hard alone is not enough to be NP-complete. It still remains to show that Hampath is in fact NP itself, but that's not the big issue here, I think.

3. A very naïve answer to your fist question is: SAT is more general than $3$-SAT, so, as a rule, you should expect it to be harder to reduce SAT to something than to reduce 3-SAT to something.

As a last comment, it would be helpful to know what exactly you don't understand in the reduction, so maybe you should try to explain what you understood so far and point out where the issue is.