Redirected from NPComplete
One example of an NPcomplete problem is the subset sum problem which is: given a finite set of integers, determine whether any nonempty subset of them adds up to zero. It's easy to check a supposed answer to see if it's right, but no one knows a fast way to solve the problem.
At present, all known algorithms for NPcomplete problems require time which is exponential in the problem size. It is unknown whether there are any faster algorithms. Therfore, in order to solve an NPcomplete problem for any nontrivial problem size, one of the following approaches is used:

A decision problem C is NPcomplete 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,
This definition was given by Stephen Cook in 1971. At first it seems rather surprising that NPcomplete problems should even exist, but in a celebrated theorem Cook proved that the Boolean satisfiability problem is NPcomplete.
It isn't really correct to say that NPcomplete 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 NPcomplete nor in P. Some of these problems may actually have higher complexity than some of the NPcomplete problems.
An interesting example is the graph theory problem 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 G_{1} isomorphic to graph G_{2}? Subgraph Isomorphism: Is graph G_{1} isomorphic to a subgraph of graph G_{2}?
The Subgraph Isomorphism problem is NPcomplete. The Graph Isomorphism problem is suspected to be neither in P nor NPcomplete, 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 NPcomplete.
The easiest way to prove that some new problem is NPcomplete is to reduce some known NPcomplete problem to it. Therefore, it is useful to know a variety of NPcomplete problems. Here are a few:
Here is a diagram of some of the NPComplete problems and their relative positions among them:
In the definition of NPcomplete given above, the term "reduction" was used in the technical meaning of polynomialtime manyone reduction. Another type of reduction is polynomialtime 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 manyone 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 NPcomplete with Turing reductions instead of manyone reductions, the resulting set of problems won't be smaller than NPcomplete; it is an open question whether it will be any larger. If the two concepts were the same, then it would follow that NP = CoNP. This holds because by their definition the classes of NPcomplete and coNPcomplete problems under Turing reductions are the same and because these classes are both supersets of the same classes defined with manyone reductions. So if both definitions of NPcompleteness are equal then there is a coNPcomplete problem (under both definitions) such as for example the complement of the boolean satisfiability problem that is also NPcomplete (under both definitions). This implies that NP = coNP as is shown in the proof in the article on coNP. Although the question of NP = coNP is an open question it is considered unlikely and therefore it is also unlikely that the two definitions of NPcompleteness are equivalent.
Another type of reduction that is also often used to define NPcompletness is the logarithmicspace manyone reduction[?] which is a manyone 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 logarithmicspace manyone reduction then there is also a polynomialtime manyone reduction. This type of reduction is more refined then the more usual polynomialtime manyone reductions and it allows us to distinguish more classes such as Pcomplete. Whether under these types of reductions the definition of NPcomplete changes is still an open problem.
Search Encyclopedia

Featured Article
