33.12.1. NP-Completeness Proofs¶

To start the process of being able to prove problems are NP-complete, we need to prove just one problem \(H\) is NP-complete. After that, to show that any problem \(X\) is NP-hard, we just need to reduce \(H\) to \(X\). When doing NP-completeness proofs, it is very important not to get this reduction backwards! If we reduce candidate problem \(X\) to known hard problem \(H\), this means that we use \(H\) as a step to solving \(X\). All that means is that we have found a (known) hard way to solve \(X\). However, when we reduce known hard problem \(H\) to candidate problem \(X\), that means we are using \(X\) as a step to solve \(H\). And if we know that \(H\) is hard, that means \(X\) must also be hard (because if \(X\) were not hard, then neither would \(H\) be hard).

So a crucial first step to getting this whole theory off the ground is finding one problem that is NP-hard. The first proof that a problem is NP-hard (and because it is in NP, therefore NP-complete) was done by Stephen Cook. For this feat, Cook won the first Turing award, which is the closest Computer Science equivalent to the Nobel Prize.

For our proofs we will use the Circuit Satisfiability Problem as the first NP-Complete problem. We will take it for a fact that Circuit Satisfiability is an NP Complete Problem.

The next few modules provide examples of reductions that can be used to prove that a particular problem is NP Complete.