NP-complete

In computational complexity theory, the complexity class NP-complete is the subset of decision problems in NP such that every problem in NP can be reduced into each of the decision problems NP-complete. It can be said that NP-complete problems are the most difficult NP problems and are most likely not part of the complexity class P. The reason is that if there is a polynomial solution for an NP-complete problem, all NP-complete problems NP would also have a solution in polynomial time.

If it were shown that an NP-complete problem, let's call it A, could not be solved in polynomial time, the rest of the NP-complete problems could not be solved in polynomial time either. This is because if one of the NP-complete problems other than A, say X, could be solved in polynomial time, then A could be solved in polynomial time, by definition of NP-complete. Now, there may be problems in NP that are not NP-complete for which there is a polynomial solution, even if there is no solution for A.

As an example of an NP-complete problem we find the subset addition problem which can be stated as follows: given a set S of integers, does there exist a non-empty subset of S whose elements sum to zero? It is easy to check if an answer is correct, but there is no known better solution than exploring all 2ⁿ-1 possible subsets until finding one that satisfies the condition.

Definition of NP-complete

A decision problem C is NP-complete if:

1. C is contained in the NP set, and
2. Any NP problem is reduced to C in polynomial time.

It can be shown that C is NP by showing that a candidate solution of C can be verified in polynomial time.

A polynomial transformation of L to C is a deterministic algorithm that transforms instances of l ∈ L into instances of c ∈ C, such that the response to c is positive if and only if the response to l it is.

As a consequence of this definition, if one had an algorithm in P for C, one would have a solution in P for all NP problems.

This definition was proposed by Stephen Cook in 1971. At first it seemed surprising that NP-complete problems exist, but Cook proved (Cook's theorem) that the Boolean satisfiability problem is NP-complete. Thousands of other problems have since been shown to belong to this class, almost always by reduction from other problems for which their NP-completeness had already been shown; many of these problems appear in Garey and Johnson's 1979 book Computers and Intractability: A Guide to NP-completeness.

A problem that satisfies the second condition belongs to the class NP-hard regardless of whether it satisfies the first.

History

The concept of "NP-complete" was introduced by Stephen Cook in an article entitled 《The complexity of theorem-proving procedures》 on pages 151-158 of Proceedings of the 3rd Annual ACM Symposium on Theory of Computing in 1971, although the term & #34;NP-full" as such it does not appear in the document. At the computer science conference there was an intense debate among computer scientists about whether NP-complete problems could be solved in polynomial time or in a deterministic Turing machine. John Hopcroft led all the conference attendees to a consensus concluding that the study on whether NP-complete problems are solvable in polynomial time should be postponed since no one had managed to formally prove their hypotheses one way or the other. This is known as the P=NP? problem.

No one has yet been able to give a final answer to this problem, making it one of the great unsolved problems of mathematics. Since May 2000, the Clay Mathematics Institute has offered a $1 million reward to anyone who can prove that P=NP or P≠NP.

Cook's Theorem shows that the Boolean satisfiability problem is an NP-complete problem. In 1972, Richard Karp proved that other problems were also NP-complete (see Karp's List of 21 NP-complete problems). Starting from the original results of Cook's Theorem, hundreds of problems have been discovered that also belong to NP-complete by reductions from other problems that had previously been shown to be NP-complete; many of these problems have been covered in Garey and Johnson's 1979 book Computers and Intractability: A Guide to NP-Completeness.

Examples

An interesting problem in graph theory is that of graph isomorphism: Two graphs are isomorphic if one can be transformed into the other simply by renaming the vertices. Of the following two problems:

Isomorphism of graphs: Is the graph G₁ isomorph to the G graph₂?

Isomorphism of subgraphs: Is the G graph₁ isomorph to a G graph subgraph₂?

The graph isomorphism problem is suspected to be neither in P nor in NP-complete, although it is in NP. This is a difficult problem, but not difficult enough to be NP-complete.

The easiest way to prove that a new problem is NP-complete is: first prove that it is in NP and then transform it, in polynomial time, into a problem that is already in NP-complete. For this it is useful to know some of the problems for which there is proof of membership in NP-completeness. Some of the most famous are:

• Bonolean Satability Problem (SAT)
• Backpack problem (knapsack)
• Problem of the Haitian cycle
• Problem of the traveler
• Clique problem

See also:

• Category:Problems NP-complete

Some NP-complete problems, indicating reductions typically used in NP completity

On the right, a diagram of some of the problems and their reductions typically used to prove their NP completeness. In this diagram, an arrow from one problem to another indicates the direction of reduction. Note that this diagram can be misleading into thinking that it shows a description of the mathematical relationship between those problems, since there is a polynomial time reduction relationship between any two NP-complete problems; but this indicates that proving these polynomial time reductions has been easier.

Often there is only a small difference between a P problem and an NP-complete problem. For example, the 3SAT problem, a constraint of the satisfiability problem, is still NP-complete, while the slightly stricter 2SAT problem is in P (specifically, NL-complete), and the slightly more general 2SAT MAX problem - is, again, NP-complete. Determining if a graph can be colored with 2 colors is in P, but with 3 colors it is NP-complete, even when restricted to planar graphs. Determining if a graph is a cycle or bipartite is very easy (in L), but finding a maximum bipartite or cycle subgraph is NP-complete. A solution of the knapsack problem within any fixed percentage of the optimal solution can be computed in polynomial time, but finding the optimal solution is NP-complete.

Approximate Solutions

Currently, all known algorithms for NP-complete problems use exponential time with respect to input size. It is unknown if there are faster algorithms, so to solve an NP-complete problem of arbitrary size, one of the following approaches is used:

• Approximately: An algorithm that quickly finds a solution not necessarily optimal, but within a certain range of error. In some cases, finding a good approximation is enough to solve the problem, but not all NP-complete problems have approximation algorithms.
• Probabilistic: A probabilistic algorithm uses randomness to obtain on average a good solution to the problem posed with a small probability to fail, for a distribution of the input data given.
• Restrictions: By restricting the input structure you can find faster algorithms.
• Individual cases: There may be recognition of particular cases of the problem for which quick solutions exist.
• Genetic algorithm: Algorithms that improve possible solutions to find one that is possibly close to the optimal. There is also no way to ensure the quality of the response.
• Heuristics: An algorithm that works reasonably well in many cases. They are generally fast, but there is no measure of the quality of the response. Metaheuristic approaches are often employed.

An example of an O(n log n) complexity heuristic algorithm is the greedy algorithm used for vertex coloring in some compilers. Because most RISC machines have a large number of general purpose registers, even a heuristic approach is effective for this application.

Completion under different types of reduction

In the definition of NP-complete given above, the term "reduction" was used in the sense of transforming instances of one problem into instances of another (many-one reductions).

Another type of reduction is the "Turing polynomial time reduction". A problem X is reducible in Turing polynomial time Y if, given a function that solves Y in polynomial time, a program could be written that, by calling the previous subroutine, solves X in polynomial time. This contrasts with the use of the term reduction that we talked about at the beginning since this has the restriction that the program can only call the subalgorithm once and the value returned by it must be the return value of the program.

If the NP-complete analogue is defined with Turing reductions instead of many-one reductions, the resulting set of problems would not be smaller than NP-complete, in fact it is questionable if they would be larger. If the two concepts were the same, it would follow that NO = Co-NP. This holds because by definition the classes of NP-complete and co-NP-complete problems under Turing reductions are the same because classes defined with many-one reductions are subclasses of these. Therefore if both definitions of NP-completeness are equal there is a co-NP-complete problem (under both definitions) such as the complementary of the Boolean satisfiability problem which is also NP-complete (under both definitions). This implies that NP = co-NP as shown as proof in the article on co-NP. Although the question of whether NP = co-NP is an open question it is considered highly unlikely because it is also highly unlikely that the two definitions of NP-completeness are equivalent.

Another type of reduction often used to define NP-completeness is the many-one log space reduction which can be computed using only one logarithmic amount of space. Since every computation that can be performed in logarithmic space can also be performed in polynomial time it is reasoned that if there is a many-one log space reduction there is also a many-one polynomial time reduction. This type of reduction is more refined than the more usual many-one polynomial time reduction and allows distinguishing more classes such as P-complete. Whether under these types of reductions changes to the definition of NP-complete is still an open problem.