Satisfiablity and Cook's Theorem

To anyone who has studied astronomy, they will know of Variable Stars. These are well known objects with well known characteristics, and we use them as ``standard candles'' when measuring distance. In likeness, it would be nice to have something in computing which will let us decide whether a problem is NP-HARD.

One such problem is the Satisfiablity problem. Let $\left\{x_1, ..., x_n\right\}$ be a set of Boolean literals. Then we write an arbitrary sentence $S = x_1 \vee x_2 \wedge ... x_n$. The Satisfiablity problem is - given an arbitrary sentence of $n$ literals, is there an assignment to each literal such that the sentence is true. In other words, can we assign $\left\{true, false\right\}$ to each $x_i$ such that $S$ will be true.

Now this is a decision problem. The answer will either be yes or no. Now, to decide whether the answer is yes or no, at worst case, we will need to make $O(2^n)$ assignments. However, suppose we are given an assignment. That is suppose we have an answer. Then, we can check that solution in $O(n)$ time. Thus, by definition of complexity classes, Satisfiablity is in NP.

Now, Cook's Theorem: Satisfiablity is NP-COMPLETE. How would one go about proving this? Cook basically showed that we can P-time reduce an arbitrary Turing Machine to the Satisfiablity problem, which is the same thing as saying that all problems in NP are P-time reducible to Satisfiablity. So, Satisfiablity is in NP and NP-HARD, which means that it must be NP-COMPLETE.

We can often use this as a ``standard candle'' in Complexity. To show that a problem $\Phi$ is NP-HARD, we simply show that Satisfiablity is P-time reducible to $\Phi$. Then we know that $\Phi$ is at least as hard as Satisfiablity, which means that it is NP-HARD.