from the 3SAT expression to the graph can be done deterministically in
polynomial time.
The point of these reductions is that we can now look at a given problem in
several ways. Suppose we conjecture that SAT is tractable. If this is difficult to
prove, we might try the simpler 3SAT case. If this does not work either, we can
try to find an efficient algorithm for the clique problem, or some other related
graph problem. If any of the options can be shown to be tractable, we can claim
that SAT is tractable.
EXERCISES
1. Show how a CNF expression with clauses of five literals can be reduced to
the 3SAT form.
Generalize your method for clauses with an arbitrary number of literals.
2. Show how the reduction of SAT to 3SAT can be done in polynomial-time.
3. Justify the statement in Example 14.10 that a 3SAT expression with k clauses
is satisfiable if and only if the associated graph has a k-clique.
4. Show that the construction of the graph associated with a 3SATexpression can
be done deterministically in polynomial-time.
* 5. The Traveling Salesman Problem (TSP) can be stated as follows. Let G be a
complete graph, whose edges are assigned nonnegative weights. The weight
of a simple path is the sum of all the edge weights. The TSP problem is to
decide if, for any given k ≥ 0, the graph G has a Hamiltonian path with a
weight less than or equal to k.
Show that HAMPATH is polynomial-time reducible to TSP.
14.7 NP-Completeness and an Open Question
There are a number of problems that are central to complexity study and are such
that, if we completely understood one of them, we would understand the major
issue involved in tractability.
polynomial time.
The point of these reductions is that we can now look at a given problem in
several ways. Suppose we conjecture that SAT is tractable. If this is difficult to
prove, we might try the simpler 3SAT case. If this does not work either, we can
try to find an efficient algorithm for the clique problem, or some other related
graph problem. If any of the options can be shown to be tractable, we can claim
that SAT is tractable.
EXERCISES
1. Show how a CNF expression with clauses of five literals can be reduced to
the 3SAT form.
Generalize your method for clauses with an arbitrary number of literals.
2. Show how the reduction of SAT to 3SAT can be done in polynomial-time.
3. Justify the statement in Example 14.10 that a 3SAT expression with k clauses
is satisfiable if and only if the associated graph has a k-clique.
4. Show that the construction of the graph associated with a 3SATexpression can
be done deterministically in polynomial-time.
* 5. The Traveling Salesman Problem (TSP) can be stated as follows. Let G be a
complete graph, whose edges are assigned nonnegative weights. The weight
of a simple path is the sum of all the edge weights. The TSP problem is to
decide if, for any given k ≥ 0, the graph G has a Hamiltonian path with a
weight less than or equal to k.
Show that HAMPATH is polynomial-time reducible to TSP.
14.7 NP-Completeness and an Open Question
There are a number of problems that are central to complexity study and are such
that, if we completely understood one of them, we would understand the major
issue involved in tractability.