Proof that SAT is NPC

Question

I am not really sure I understand the idea behind Cook theorem (it says that SAT is a NP-complete problem).

I read the proof with all its parts corresponding to the Turing machine TM solving it (TM is in a single state at any given time, only single cell is read by the head of TM in every single moment, only single symbol is on the tape etc...) + the fact that SAT is in NP (which is obvious)

... but I just dont understand how does it all prove anything?

The definition of NP-complete problem is, that a problem $U$ is in NPC, if all NP problems are polynomially reducible to $U$ and $U$ is in NP.

I understand that I can prove that some problem $V$ is in NPC, if I find another problem $W$ in NPC which is reducible to $V$ and check that $V$ is in NP (otherwise, it would be NP-hard, right?) so I basically need at least one problem to be known as NPC so I can begin with the reductions to other problems (and this problem is SAT as a root of this proof tree).

How does the long proof based on the work of TM actually prove that SAT is NPC? I cant posiibly prove that all NP problems can be reduced to SAT in this way, or can I?

Answer 1

A language $L$ is “NP-complete” if $L$ belongs to NP, and every language $X$ in NP can be polynomial-time reduced to $L$; that is the definition of “NP-complete”.

How might we show that every problem $X$ in NP can be reduced to $L$?

Well, $X$ is in NP, and the only thing we have to work with here is the definition of NP:

There is a nondeterministic Turing machine $M$ which,
given a string $I$,
correctly decides in polynomial time
whether $I$ is in $X$.

Cook's theorem takes $M$ and a specific $I$ and constructs a large (but polynomial) family of statements that are satisfiable if, and only if, $M$ will accept $I$.

The statements do this because they completely describe the exact computation that $M$ would perform starting with string $I$, including an assertion that $M$ would end in an accepting state.

Because of the way the statements are constructed, they can be satisfied if, and only if, $M$ would actually perform a computation that ends by accepting $I$. If there is no such computation, the clauses are not satisfiable.

So we have this large (but polynomial) family of statements which are satisfiable if, and only if, the machine $M$, which correctly recognizes the language $X$, would accept the particular string $I$.

If we had a satisfying assignment for those statements, that satisfying assignment would exactly describe what $M$ would do in accepting $I$: it would say how $M$ would move its head, and how it would modify the tape over time, and so on, and it would also describe the fact that $M$ would terminate in an accepting state.

So if we could find a satisfying assignment for this large family of statements, we would know that $I$ was in $X$, because we would have a complete description of how the machine $M$, which recognizes $X$, would behave in accepting $I$.

If we could quickly find a satisfying assignment for this large (but polynomial) family of statements, we would be able to quickly decide whether any given $I$ was in $X$, as follows: We would take the string $I$. We would construct the large (but polynomial) family of statements that collectively describe $M$'s computation starting with $I$, including the assertion that $M$ would end in an accepting state. We would quickly check if those statements were satisfiable. If they were, we would know that $M$ would accept $I$; if not then not.

But if we could quickly find satisfying assignments, we could quickly solve every problem $X$ that is in NP, because for every such problem $X$ there is a machine $M$ that recognizes $X$. So an efficient solution to the satisfiability problem would give us an efficient solution to problem $X$ that was in NP. If $X$ is in NP, there is some machine $M$ that recognizes it, and then given any string $I$, we could do just as in the previous paragraph to quickly decide whether $I$ was in $X$.

So an efficient method for finding satisfying assignments can solve efficiently solve any problem $X$ in NP:

Take the machine $M$ that recognizes $X$, construct a set of statements that describe its computation starting from $I$, including the assertion that the computation would end in an accepting state, and then check if those statements can be satisfied. If so, then $I$ is in $X$.

I hope that was some help.

Answer 2

Since $\mathrm{SAT}$ is the first problem proven to be NP-complete, Cook proved that $\mathrm{SAT}$ is NP-complete using the basic definition of NP-completeness which says that to prove that a problem is NP-complete if all NP problems are reducible to it in polynomial time. So, Cook did this using the Turing Machine concept.

After Cook's work, life is made "easier". To prove that a problem is NP-complete you only need to find an NP-hard problem and reduce it to your problem then prove that your problem is in NP to get the NP-completeness for your problem.

Look at Richard Karp's paper to see how the reductions of a bench of problems work and how Karp did to prove that some problems are NP-complete based on reduction from $\mathrm{SAT}$.

I hope this helps.