Java Reference
In-Depth Information
so this algorithm cannot be converted to a polynomial time algorithm on a regu-
lar computer. Nor does anybody in the world know of any other polynomial time
algorithm to solve TRAVELING SALESMAN on a regular computer, despite the
fact that the problem has been studied extensively by many computer scientists for
many years.
It turns out that there is a large collection of problems with this property: We
know efficient non-deterministic algorithms, but we do not know if there are effi-
cient deterministic algorithms. At the same time, we have not been able to prove
that any of these problems do not have efficient deterministic algorithms. This class
of problems is called NP-complete. What is truly strange and fascinating about
NP-complete problems is that if anybody ever finds the solution to any one of
them that runs in polynomial time on a regular computer, then by a series of reduc-
tions, every other problem that is in NP can also be solved in polynomial time on
a regular computer!
Define a problem to be NP-hard if any problem in NP can be reduced to X
in polynomial time. Thus, X is as hard as any problem in NP. A problem X is
defined to be NP-complete if
1. X is in NP, and
2. X is NP-hard.
The requirement that a problem be NP-hard might seem to be impossible, but
in fact there are hundreds of such problems, including TRAVELING SALESMAN.
Another such problem is called K-CLIQUE.
K-CLIQUE
Input: An arbitrary undirected graph G and an integer k.
Output: YES if there is a complete subgraph of at least k vertices, and NO
otherwise.
Nobody knows whether there is a polynomial time solution for K-CLIQUE, but if
such an algorithm is found for K-CLIQUE or for TRAVELING SALESMAN, then
that solution can be modified to solve the other, or any other problem in NP, in
polynomial time.
The primary theoretical advantage of knowing that a problem P1 is NP-comp-
lete is that it can be used to show that another problem P2 is NP-complete. This is
done by finding a polynomial time reduction of P1 to P2. Because we already know
that all problems in NP can be reduced to P1 in polynomial time (by the definition
of NP-complete), we now know that all problems can be reduced to P2 as well by
the simple algorithm of reducing to P1 and then from there reducing to P2.
There is a practical advantage to knowing that a problem is NP-complete. It
relates to knowing that if a polynomial time solution can be found for any prob-
