Java Reference
In-Depth Information
for TRAVELING SALESMAN and all related problems. Because TRAVELING
SALESMAN is known to be NP-complete, if a polynomial time algorithm were to
be found for this problem, then all problems in NP would also be solvable in poly-
nomial time. Conversely, if we were able to prove that TRAVELING SALESMAN
has an exponential time lower bound, then we would know that P 6= NP.
17.2.2
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 can-
didate 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. The “grand-daddy” NP-complete problem that Cook used is
call SATISFIABILITY (or SAT for short).
A Boolean expression includes Boolean variables combined using th
e o
pera-
tors AND (), OR (+), and NOT (to negate Boolean variable x we write x). A
literal is a Boolean variable or its negation. A clause is one or more literals OR'ed
together. Let E be a Boolean expression over variables x
1
;x
2
;:::;x
n
. Then we
define Conjunctive Normal Form (CNF) to be a Boolean expression written as a
series of clauses that are AND'ed together. For example,
E = (x
5
+ x
7
+ x
8
+ x
10
) (x
2
+ x
3
) (x
1
+ x
3
+ x
6
)
is in CNF, and has three clauses. Now we can define the problem SAT.
SATISFIABILITY (SAT)
Input: A Boolean expression E over variables x
1
;x
2
;::: in Conjunctive Nor-
mal Form.
Output: YES if there is an assignment to the variables that makes E true,
NO otherwise.
Cook proved that SAT is NP-hard.
Explaining Cook's proof is beyond the
scope of this topic.
But we can briefly summarize it as follows.
Any decision
