We have shown that SAT can be reduced to 3SAT, and that 3SAT can be reduced
to CLIQ. Therefore 3SAT and CLIQ are both NP-complete.
It turns out that HAMPATH is also NP-complete, but the reductions needed
to show this are less obvious.
In addition to SAT, 3SAT, CLIQ, and HAMPATH, there are many more
problems that are known to be NP-complete. A good deal of effort has been
expended in trying to find efficient algorithms for any of these, so far without
success. This leads us to conjecture that
P ≠ NP
and that many important problems are intractable. But while this is a reasonable
working conjecture, it has not been proved. It remains the fundamental open
problem in complexity theory.
EXERCISES
1. Show that TSP is NP-complete.
* 2. Let G be an undirected graph. An Euler circuit of the graph is a simple
cycle that includes all edges. The Euler Circuit Problem (EULER) is to
decide if G has an Euler circuit.
Show that EULER is not NP-complete.
3. Consult books on complexity theory to compile a list of NP-complete
problems.
4. Is it possible that P = NP is undecidable?
* This estimate depends on how we visualize this process and can be improved. But this is of no concern,
as we do not distinguish between the degrees of polynomials
† The second subscripts identify the group to which the vertices belong.
to CLIQ. Therefore 3SAT and CLIQ are both NP-complete.
It turns out that HAMPATH is also NP-complete, but the reductions needed
to show this are less obvious.
In addition to SAT, 3SAT, CLIQ, and HAMPATH, there are many more
problems that are known to be NP-complete. A good deal of effort has been
expended in trying to find efficient algorithms for any of these, so far without
success. This leads us to conjecture that
P ≠ NP
and that many important problems are intractable. But while this is a reasonable
working conjecture, it has not been proved. It remains the fundamental open
problem in complexity theory.
EXERCISES
1. Show that TSP is NP-complete.
* 2. Let G be an undirected graph. An Euler circuit of the graph is a simple
cycle that includes all edges. The Euler Circuit Problem (EULER) is to
decide if G has an Euler circuit.
Show that EULER is not NP-complete.
3. Consult books on complexity theory to compile a list of NP-complete
problems.
4. Is it possible that P = NP is undecidable?
* This estimate depends on how we visualize this process and can be improved. But this is of no concern,
as we do not distinguish between the degrees of polynomials
† The second subscripts identify the group to which the vertices belong.