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 be a set of Boolean literals. Then we write an arbitrary sentence . The Satisfiablity problem is - given an arbitrary sentence of literals, is there an assignment to each literal such that the sentence is true. In other words, can we assign to each such that 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 assignments. However, suppose we are given an assignment. That is suppose we have an answer. Then, we can check that solution in 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 is NP-HARD, we simply show that Satisfiablity is P-time reducible to . Then we know that is at least as hard as Satisfiablity, which means that it is NP-HARD.
Menaka Lashitha Bandara 2005-04-18