|
In complexity theory, the
NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to
solve an NP-complete problem quickly, then you could use that algorithm to solve all NP problems quickly. (A more formal
definition is given below. See also Complexity
classes P and NP).
One example of an NP-complete problem is the subset sum
problem which is: given a finite set of integers, determine whether any non-empty subset of them adds up to zero. A supposed
answer is very easy to verify for correctness, but no-one knows a significantly faster way to solve the problem than to try every
single possible subset, which is very slow.
Imperfect solutions
At present, all known algorithms for NP-complete problems require time that is
exponential in the problem size. It is unknown whether there are any faster algorithms. Therefore, to solve an NP-complete
problem for any nontrivial problem size, one of the following approaches is used:
- Approximation: An algorithm that
quickly finds a suboptimal solution that is within a certain (known) range of the optimal one. Not all NP-complete problems have
good approximation algorithms, and for some problems finding a good approximation algorithm is enough to solve the problem
itself.
- Probabilistic: An algorithm that provably yields good average runtime behavior for a given distribution of
the problem instances—ideally, one that assigns low probability to "hard" inputs.
- Special cases: An algorithm that is provably fast if the problem instances belong to a certain special case.
Fixed-parameter algorithms can be seen as an
implementation of this approach.
- Heuristic: An algorithm that works "reasonably well" on many cases, but for which there is no proof that it
is always fast.
Formal definition of NP-completeness
A decision problem C is NP-complete if it is in NP and if every other problem in NP is reducible to it. "Reducible"
here means that for every NP problem L, there is a polynomial-time algorithm which transforms instances of L into instances of C, such that
the two instances have the same truth values. As a consequence, if we had a polynomial time algorithm for C, we could
solve all NP problems in polynomial time.
In mathematical terms,
- L in NP
- L' ≤ L for every L' in NP
This definition was given by Stephen Cook in 1971. At first it seems
rather surprising that NP-complete problems should even exist, but in a celebrated theorem Cook proved that the Boolean satisfiability problem is NP-complete.
Since Cook's original results, thousands of other problems have been shown to be NP-complete by reductions from other problems
previously shown to be NP-complete; many of these problems are collected in (Garey and Johnson, 1979).
It isn't really correct to say that NP-complete problems are the hardest problems in NP. Assuming that P and NP are not equal,
there are guaranteed to be an infinite number of problems that are in NP, but are neither NP-complete nor in P. Some of these
problems may actually have higher complexity than some of the NP-complete problems.
Example problems
An interesting example is the problem, in graph theory, of graph
isomorphism. Two graphs are isomorphic if one can be transformed into the
other simply by renaming vertices. Consider these two problems:
Graph Isomorphism: Is graph G1 isomorphic to graph G2?
Subgraph Isomorphism: Is graph G1 isomorphic to a subgraph of graph G2?
The Subgraph Isomorphism problem is NP-complete. The Graph Isomorphism problem is suspected to be neither in P nor
NP-complete, though it is obviously in NP. This is an example of a problem that is thought to be hard, but isn't thought to be
NP-complete.
The easiest way to prove that some new problem is NP-complete is first to prove that it is in NP, and then to reduce some
known NP-complete problem to it. Therefore, it is useful to know a variety of NP-complete problems. Here are a few:
Here is a diagram of some of the NP-Complete problems and the reductions typically used to prove their NP-completeness. In
this diagram, an arrow from one problem to another indicates the direction of the reduction. Note that this diagram is misleading
as a description of the mathematical relationship between these problems, as there exists a polynomial-time reduction between any
two NP-complete problems; but it indicates where demonstrating this polynomial-time reduction has been easiest.
Alternative approaches
In the definition of NP-complete given above, the term "reduction" was used in the technical meaning of polynomial-time many-one reduction.
Another type of reduction is polynomial-time Turing reduction. A problem X is polynomial-time Turing-reducible
to a problem Y if, given a subroutine that solves Y in polynomial time, you could write a program that calls
this subroutine and solves X in polynomial time. This contrasts with many-one reducibility, which has the restriction
that the program can only call the subroutine once, and the return value of the subroutine must be the return value of the
program.
If one defines the analogue to NP-complete with Turing reductions instead of many-one reductions, the resulting set of
problems won't be smaller than NP-complete; it is an open question whether it will be any larger. If the two concepts were the
same, then it would follow that NP = Co-NP. This holds because by their definition the
classes of NP-complete and co-NP-complete problems under Turing reductions are the same and because these classes are both
supersets of the same classes defined with many-one reductions. So if both definitions of NP-completeness are equal then there is
a co-NP-complete problem (under both definitions) such as for example the complement of the boolean satisfiability problem that
is also NP-complete (under both definitions). This implies that NP = co-NP as is shown in the proof in the article on co-NP. Although the question of NP = co-NP is an open question it is considered unlikely and
therefore it is also unlikely that the two definitions of NP-completeness are equivalent.
Another type of reduction that is also often used to define NP-completness is the logarithmic-space many-one reduction which is a many-one reduction that can be
computed with only a logarithmic amount of space. Since every computation that can be done in logarithmic space can also be done
in polynomial time it follows that if there is a logarithmic-space many-one reduction then there is also a polynomial-time
many-one reduction. This type of reduction is more refined than the more usual polynomial-time many-one reductions and it allows
us to distinguish more classes such as P-complete. Whether under these types of
reductions the definition of NP-complete changes is still an open problem.
References
- Garey, M. and D. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness, 1979. ISBN 0716710455 (This book is a classic,
developing the theory, then cataloging many NP-Complete problems)
- S. A. Cook, The complexity of theorem proving procedures, Proceedings, Third Annual ACM Symposium on the Theory of Computing,
ACM, New York, 1971, 151-158
- Computational Complexity of Games and Puzzles
- Tetris is Hard, Even
to Approximate
- Minesweeper is NP-complete!
|