 | This articlemay beconfusing or unclear to readers. Please helpclarify the article. There might be a discussion about this onthe talk page.(July 2012) (Learn how and when to remove this message) |
Incomputational complexity theory, a problem isNP-complete when:
The name "NP-complete" is short for "nondeterministic polynomial-time complete". In this name, "nondeterministic" refers tonondeterministic Turing machines, a way of mathematically formalizing the idea of a brute-force search algorithm.Polynomial time refers to an amount of time that is considered "quick" for adeterministic algorithm to check a single solution, or for a nondeterministic Turing machine to perform the whole search. "Complete" refers to the property of being able to simulate everything in the samecomplexity class.
More precisely, each input to the problem should be associated with a set of solutions of polynomial length, the validity of each of which can be tested quickly (inpolynomial time),[2] such that the output for any input is "yes" if the solution set is non-empty and "no" if it is empty. The complexity class of problems of this form is calledNP, an abbreviation for "nondeterministic polynomial time". A problem is said to beNP-hard if everything in NP can be transformed in polynomial time into it even though it may not be in NP. A problem is NP-complete if it is both in NP and NP-hard. The NP-complete problems represent the hardest problems in NP. If some NP-complete problem has a polynomial time algorithm, all problems in NP do. The set of NP-complete problems is often denoted byNP-C orNPC.
Although a solution to an NP-complete problem can beverified "quickly", there is no known way tofind a solution quickly. That is, the time required to solve the problem using any currently knownalgorithm increases rapidly as the size of the problem grows. As a consequence, determining whether it is possible to solve these problems quickly, called theP versus NP problem, is one of the fundamentalunsolved problems in computer science today.
While a method for computing the solutions to NP-complete problems quickly remains undiscovered,computer scientists andprogrammers still frequently encounter NP-complete problems. NP-complete problems are often addressed by usingheuristic methods andapproximation algorithms.
NP-complete problems are inNP, the set of alldecision problems whose solutions can be verified in polynomial time;NP may be equivalently defined as the set of decision problems that can be solved in polynomial time on anon-deterministic Turing machine. A problemp in NP is NP-complete if every other problem in NP can be transformed (or reduced) intop in polynomial time.[citation needed]
It is not known whether every problem in NP can be quickly solved—this is called theP versus NP problem. But ifany NP-complete problem can be solved quickly, thenevery problem in NP can, because the definition of an NP-complete problem states that every problem in NP must be quickly reducible to every NP-complete problem (that is, it can be reduced in polynomial time). Because of this, it is often said that NP-complete problems areharder ormore difficult than NP problems in general.[citation needed]
A decision problem is NP-complete if:[citation needed]
can be shown to be in NP by demonstrating that a candidate solution to can be verified in polynomial time.
Note that a problem satisfying condition 2 is said to beNP-hard, whether or not it satisfies condition 1.[4]
A consequence of this definition is that if we had a polynomial time algorithm (on aUTM, or any otherTuring-equivalentabstract machine) for, we could solve all problems in NP in polynomial time.
The concept of NP-completeness was introduced in 1971 (seeCook–Levin theorem), though the termNP-complete was introduced later. At the 1971STOC conference, there was a fierce debate between the computer scientists about whether NP-complete problems could be solved in polynomial time on adeterministicTuring machine.John Hopcroft brought everyone at the conference to a consensus that the question of whether NP-complete problems are solvable in polynomial time should be put off to be solved at some later date, since nobody had any formal proofs for their claims one way or the other.[citation needed] This is known as "the question of whether P=NP".
Nobody has yet been able to determine conclusively whether NP-complete problems are in fact solvable in polynomial time, making this one of the greatunsolved problems of mathematics. TheClay Mathematics Institute is offering a US$1 million reward (Millennium Prize) to anyone who has a formal proof that P=NP or that P≠NP.[5]
The existence of NP-complete problems is not obvious. TheCook–Levin theorem states that theBoolean satisfiability problem is NP-complete, thus establishing that such problems do exist. In 1972,Richard Karp proved that several other problems were also NP-complete (seeKarp's 21 NP-complete problems); thus, there is a class of NP-complete problems (besides the Boolean satisfiability problem). Since the 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 inGarey & Johnson (1979).
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. The list below contains some well-known problems that are NP-complete when expressed as decision problems.
To the right is a diagram of some of the problems and thereductions typically used to prove their NP-completeness. In this diagram, problems are reduced from bottom to top. Note that this diagram is misleading as a description of the mathematical relationship between these problems, as there exists apolynomial-time reduction between any two NP-complete problems; but it indicates where demonstrating this polynomial-time reduction has been easiest.
There is often only a small difference between a problem in P and an NP-complete problem. For example, the3-satisfiability problem, a restriction of the Boolean satisfiability problem, remains NP-complete, whereas the slightly more restricted2-satisfiability problem is in P (specifically, it isNL-complete), but the slightly more general max. 2-sat. problem is again NP-complete. Determining whether a graph can be colored with 2 colors is in P, but with 3 colors is NP-complete, even when restricted toplanar graphs. Determining if a graph is acycle or isbipartite is very easy (inL), but finding a maximum bipartite or a maximum cycle subgraph is NP-complete. A solution of theknapsack problem within any fixed percentage of the optimal solution can be computed in polynomial time, but finding the optimal solution is NP-complete.
An interesting example is thegraph isomorphism problem, thegraph theory problem of determining whether agraph isomorphism exists between two graphs. Two graphs areisomorphic if one can betransformed into the other simply by renamingvertices. Consider these two problems:
The Subgraph Isomorphism problem is NP-complete. The graph isomorphism problem is suspected to be neither in P nor NP-complete, though it is in NP. This is an example of a problem that is thought to behard, but is not thought to be NP-complete. This class is calledNP-Intermediate problems and exists if and only if P≠NP.
At present, all known algorithms for NP-complete problems require time that issuperpolynomial in the input size. Thevertex cover problem has[6] for some and it is unknown whether there are any faster algorithms.
The following techniques can be applied to solve computational problems in general, and they often give rise to substantially faster algorithms:
One example of a heuristic algorithm is a suboptimalgreedy coloring algorithm used forgraph coloring during theregister allocation phase of some compilers, a technique calledgraph-coloring global register allocation. Each vertex is a variable, edges are drawn between variables which are being used at the same time, and colors indicate the register assigned to each variable. Because mostRISC machines have a fairly large number of general-purpose registers, even a heuristic approach is effective for this application.
In the definition of NP-complete given above, the termreduction was used in the technical meaning of a polynomial-timemany-one reduction.
Another type of reduction is polynomial-timeTuring reduction. A problem is polynomial-time Turing-reducible to a problem if, given a subroutine that solves in polynomial time, one could write a program that calls this subroutine and solves 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.
Another type of reduction that is also often used to define NP-completeness is thelogarithmic-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 inlogarithmic 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 asP-complete. Whether under these types of reductions the definition of NP-complete changes is still an open problem. All currently known NP-complete problems are NP-complete under log space reductions. All currently known NP-complete problems remain NP-complete even under much weaker reductions such as reductions and reductions. Some NP-Complete problems such as SAT are known to be complete even under polylogarithmic time projections.[7] It is known, however, thatAC0 reductions define a strictly smaller class than polynomial-time reductions.[8]
According toDonald Knuth, the name "NP-complete" was popularized byAlfred Aho,John Hopcroft andJeffrey Ullman in their celebrated textbook "The Design and Analysis of Computer Algorithms". He reports that they introduced the change in thegalley proofs for the book (from "polynomially-complete"), in accordance with the results of a poll he had conducted of thetheoretical computer science community.[9] Other suggestions made in the poll[10] included "Herculean", "formidable",Steiglitz's "hard-boiled" in honor of Cook, and Shen Lin's acronym "PET", which stood for "probably exponential time", but depending on which way theP versus NP problem went, could stand for "provably exponential time" or "previously exponential time".[11]
The following misconceptions are frequent.[12]
Viewing adecision problem as a formal language in some fixed encoding, the set NPC of all NP-complete problems isnot closed under:
It is not known whether NPC is closed undercomplementation, since NPC=co-NPC if and only if NP=co-NP, and since NP=co-NP is anopen question.[16]
The question of whether NP and co-NP are equal is probably the second most important open problem in complexity theory, after the P versus NP question.