NP-complete Problems

Question

It seems from reading that problems are determined to be NP-complete if they can be shown to be equivalent to another NP-complete problem. However, I wonder how the "original" NP-complete problem was shown to be NP-complete. If one could say how this was done, I would be grateful.

Answer 1

As MJD pointed out, Garey and Johnson provide a very readable explanation of why SAT is NP-complete. The basic idea is very simple (and elegant), but the details involve no small amount of complication. Here's a pared-down explanation.

NP problems: A decision problem $X$ is in NP if, by definition, there is some nondeterministic Turing Machine $M$ such that when $M$ is given an instance, $I$ of $X$ as its input, can decide in time polynomial in the length of $I$ whether $I$ has a solution or not.

NP-Complete problems: A decision $Y$ problem in NP is called NP-complete if for any problem $X\in$ NP, there is a polynomial-time transformation $f$ which maps an instance $I$ of $X$ into an instance $f(I)$ of $Y$, in such a way that $I$ has a solution if and only if $f(I)$ has a solution. It seems as if showing that $Y$ is NP-complete should be really intimidating: how on earth would we establish that every NP problem could be poly-time transformed to our $Y$?

SAT, a special NP problem: Recall that the decision problem SAT consists of instances $I$ which are boolean expressions over a set $V$ of boolean variables. It's not too hard to show that there is a nondeterministic TM $M$ which, when given an instance $I$, can determine, in time polynomial in the length of $I$, whether there is an assignment of values to $V$ which will make $I$ true or whether there is no such assignment (essentially, just nondeterministically generate all possible assignments and test each for satisfiability).

SAT is NP-complete: Here comes the clever part. If we want to show that SAT is NP-complete, we need to be able to transform any NP problem, $X$ to SAT. There are hundreds of NP problems, of widely varying forms; how could we possibly transform each of these into instances of SAT? Well, the only thing all of the NP problems have in common is that they can be decided by TMs, so we rely on that property. For any NP problem $X$ we express its decider TM, $M_X$ by a huge boolean expression $B$ in such a way that for an instance $I$ of $X$, $M_X(I)$ will answer "yes" if and only if $B$ can be satisfied. In essence, we're modeling the action of the TM $M_X$ on $I$. Once we do that and show that the transformation can be accomplished in polynomial time, we will have shown that SAT is indeed NP-complete.

All the important work is in the details: for instance, we need a boolean expression that represents "$M_X$ can only be in one state at a time", another that says "from this configuration, $M_X$ can only make a move to these other configurations" and so on. (I once did this for a one-move TM; it required 16 variables and 38 subclauses ANDed together. Ugh, but the point is that it can always be done.)