In computational complexity theory , a problem is NP-complete when:
53-424: The name "NP-complete" is short for "nondeterministic polynomial-time complete". In this name, "nondeterministic" refers to nondeterministic 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 a deterministic algorithm to check a single solution, or for a nondeterministic Turing machine to perform
106-404: A decision problem as a formal language in some fixed encoding, the set NPC of all NP-complete problems is not closed under: It is not known whether NPC is closed under complementation , since NPC= co-NPC if and only if NP= co-NP , and since NP=co-NP is an open question . Nondeterministic Turing machine In theoretical computer science , a nondeterministic Turing machine ( NTM )
159-486: A graph isomorphism exists between two graphs. Two graphs are isomorphic if one can be transformed into the other simply by renaming vertices . 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 be hard , but is not thought to be NP-complete. This class
212-434: A DTM can also be solved by a NTM, and vice versa. However, it is believed that in general the time complexity may not be the same. NTMs include DTMs as special cases, so every computation that can be carried out by a DTM can also be carried out by the equivalent NTM. It might seem that NTMs are more powerful than DTMs, since they can allow trees of possible computations arising from the same initial configuration, accepting
265-438: A Turing Machine's rules might thus be: "If you are in state 2 and you see an 'A', then change it to 'B', move left, and switch to state 3." In a deterministic Turing machine (DTM), the set of rules prescribes at most one action to be performed for any given situation. A deterministic Turing machine has a transition function that, for a given state and symbol under the tape head, specifies three things: For example, an X on
318-412: A consequence, finding a polynomial time algorithm to solve a single NP-hard problem would give polynomial time algorithms for all the problems in the complexity class NP . As it is suspected, but unproven, that P≠NP , it is unlikely that any polynomial-time algorithms for NP-hard problems exist. A simple example of an NP-hard problem is the subset sum problem . Informally, if H is NP-hard, then it
371-421: A different level. All NP-complete problems are also NP-hard (see List of NP-complete problems ). For example, the optimization problem of finding the least-cost cyclic route through all nodes of a weighted graph—commonly known as the travelling salesman problem —is NP-hard. The subset sum problem is another example: given a set of integers, does any non-empty subset of them add up to zero? That
424-428: A polynomial time algorithm, all problems in NP do. The set of NP-complete problems is often denoted by NP-C or NPC . Although a solution to an NP-complete problem can be verified "quickly", there is no known way to find a solution quickly. That is, the time required to solve the problem using any currently known algorithm increases rapidly as the size of the problem grows. As a consequence, determining whether it
477-445: A quantum computer can indeed be in a superposition state corresponding to all possible computational branches having been executed at the same time (similar to an NTM), the final measurement will collapse the quantum computer into a randomly selected branch. This branch then does not, in general, represent the sought-for solution, unlike the NTM, which is allowed to pick the right solution among
530-451: A string if any one branch in the tree accepts it. However, it is possible to simulate NTMs with DTMs, and in fact this can be done in more than one way. One approach is to use a DTM of which the configurations represent multiple configurations of the NTM, and the DTM's operation consists of visiting each of them in turn, executing a single step at each visit, and spawning new configurations whenever
583-400: A subroutine that solves Y {\displaystyle \scriptstyle Y} in polynomial time, one could write a program that calls this subroutine and solves X {\displaystyle \scriptstyle 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
SECTION 10
#1732883494485636-399: Is NP-complete if: C {\displaystyle \scriptstyle C} can be shown to be in NP by demonstrating that a candidate solution to C {\displaystyle \scriptstyle C} can be verified in polynomial time. Note that a problem satisfying condition 2 is said to be NP-hard , whether or not it satisfies condition 1. A consequence of this definition
689-482: 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 the reductions typically used to prove their NP-completeness. In this diagram, problems are reduced from bottom to top. Note that this diagram
742-414: Is a cycle or is bipartite is very easy (in L ), but finding a maximum bipartite or a maximum 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. An interesting example is the graph isomorphism problem , the graph theory problem of determining whether
795-495: Is a decision problem and happens to be NP-complete. There are decision problems that are NP-hard but not NP-complete such as the halting problem . That is the problem which asks "given a program and its input, will it run forever?" That is a yes / no question and so is a decision problem. It is easy to prove that the halting problem is NP-hard but not NP-complete. For example, the Boolean satisfiability problem can be reduced to
848-511: 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
901-449: Is a theoretical model of computation whose governing rules specify more than one possible action when in some given situations. That is, an NTM's next state is not completely determined by its action and the current symbol it sees, unlike a deterministic Turing machine . NTMs are sometimes used in thought experiments to examine the abilities and limits of computers. One of the most important open problems in theoretical computer science
954-458: Is at least as difficult to solve as the problems in NP . However, the opposite direction is not true: some problems are undecidable , and therefore even more difficult to solve than all problems in NP, but they are probably not NP-hard (unless P=NP). A decision problem H is NP-hard when for every problem L in NP, there is a polynomial-time many-one reduction from L to H . Another definition
1007-406: Is called NP-Intermediate problems and exists if and only if P≠NP. At present, all known algorithms for NP-complete problems require time that is superpolynomial in the input size. The vertex cover problem has O ( 1.2738 k + n k ) {\displaystyle O(1.2738^{k}+nk)} for some k > 0 {\displaystyle k>0} and it
1060-507: Is called the P versus NP problem . But if any NP-complete problem can be solved quickly, then every 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 are harder or more difficult than NP problems in general. A decision problem C {\displaystyle \scriptstyle C}
1113-426: Is common to omit the stationary (0) output, and instead insert the transitive closure of any desired stationary transitions. Some authors add an explicit reject state, which causes the NTM to halt without accepting. This definition still retains the asymmetry that any nondeterministic branch can accept, but every branch must reject for the string to be rejected. Any computational problem that can be solved by
SECTION 20
#17328834944851166-413: Is empty. The complexity class of problems of this form is called NP , an abbreviation for "nondeterministic polynomial time". A problem is said to be NP-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
1219-438: Is known, however, that AC reductions define a strictly smaller class than polynomial-time reductions. According to Donald Knuth , the name "NP-complete" was popularized by Alfred Aho , John Hopcroft and Jeffrey Ullman in their celebrated textbook "The Design and Analysis of Computer Algorithms". He reports that they introduced the change in the galley proofs for the book (from "polynomially-complete"), in accordance with
1272-411: 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. There is often only a small difference between a problem in P and an NP-complete problem. For example, the 3-satisfiability problem, a restriction of
1325-742: Is not obvious. The Cook–Levin theorem states that the Boolean 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 (see Karp'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 in Garey & Johnson (1979) . The easiest way to prove that some new problem
1378-477: Is possible to solve these problems quickly, called the P versus NP problem , is one of the fundamental unsolved problems in computer science today. While a method for computing the solutions to NP-complete problems quickly remains undiscovered, computer scientists and programmers still frequently encounter NP-complete problems. NP-complete problems are often addressed by using heuristic methods and approximation algorithms . NP-complete problems are in NP ,
1431-476: Is sometimes a misconception that quantum computers are NTMs. However, it is believed by experts (but has not been proven) that the power of quantum computers is, in fact, incomparable to that of NTMs; that is, problems likely exist that an NTM could efficiently solve that a quantum computer cannot and vice versa. In particular, it is likely that NP-complete problems are solvable by NTMs but not by quantum computers in polynomial time. Intuitively speaking, while
1484-406: Is that if we had a polynomial time algorithm (on a UTM , or any other Turing-equivalent abstract machine ) for C {\displaystyle \scriptstyle C} , we could solve all problems in NP in polynomial time. The concept of NP-completeness was introduced in 1971 (see Cook–Levin theorem ), though the term NP-complete was introduced later. At the 1971 STOC conference, there
1537-454: Is that, for deterministic Turing machines, the transition relation is a function rather than just a relation. Configurations and the yields relation on configurations, which describes the possible actions of the Turing machine given any possible contents of the tape, are as for standard Turing machines, except that the yields relation is no longer single-valued. (If the machine is deterministic,
1590-499: Is the P versus NP problem , which (among other equivalent formulations) concerns the question of how difficult it is to simulate nondeterministic computation with a deterministic computer. In essence, a Turing machine is imagined to be a simple computer that reads and writes symbols one at a time on an endless tape by strictly following a set of rules. It determines what action it should perform next according to its internal state and what symbol it currently sees . An example of one of
1643-844: Is to require that there be a polynomial-time reduction from an NP-complete problem G to H . As any problem L in NP reduces in polynomial time to G , L reduces in turn to H in polynomial time so this new definition implies the previous one. It does not restrict the class NP-hard to decision problems, and it also includes search problems or optimization problems . If P ≠ NP, then NP-hard problems could not be solved in polynomial time. Some NP-hard optimization problems can be polynomial-time approximated up to some constant approximation ratio (in particular, those in APX ) or even up to any approximation ratio (those in PTAS or FPTAS ). There are many classes of approximability, each one enabling approximation up to
NP-completeness - Misplaced Pages Continue
1696-416: Is to say that the machine is the "luckiest possible guesser"; it always picks a transition that eventually leads to an accepting state, if there is such a transition. The other is to imagine that the machine " branches " into many copies, each of which follows one of the possible transitions. Whereas a DTM has a single "computation path" that it follows, an NTM has a "computation tree". If at least one branch of
1749-409: 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 suboptimal O ( n log n ) {\displaystyle O(n\log n)} greedy coloring algorithm used for graph coloring during
1802-426: The register allocation phase of some compilers, a technique called graph-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 most RISC machines have a fairly large number of general-purpose registers, even a heuristic approach is effective for this application. In
1855-455: The Boolean satisfiability problem, remains NP-complete, whereas the slightly more restricted 2-satisfiability problem is in P (specifically, it is NL-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 to planar graphs . Determining if a graph
1908-454: The constructed DTM effectively performs a breadth-first search of the NTM's computation tree, visiting all possible computations of the NTM in order of increasing length until it finds an accepting one. Therefore, the length of an accepting computation of the DTM is, in general, exponential in the length of the shortest accepting computation of the NTM. This is believed to be a general property of simulations of NTMs by DTMs. The P = NP problem ,
1961-526: 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 A C 0 {\displaystyle AC_{0}} reductions and N C 0 {\displaystyle NC_{0}} reductions. Some NP-Complete problems such as SAT are known to be complete even under polylogarithmic time projections. It
2014-403: The definition of NP-complete given above, the term reduction was used in the technical meaning of a polynomial-time many-one reduction . Another type of reduction is polynomial-time Turing reduction . A problem X {\displaystyle \scriptstyle X} is polynomial-time Turing-reducible to a problem Y {\displaystyle \scriptstyle Y} if, given
2067-407: The exponentially many branches. NP-hard In computational complexity theory , a computational problem H is called NP-hard if, for every problem L which can be solved in non-deterministic polynomial-time , there is a polynomial-time reduction from L to H . That is, assuming a solution for H takes 1 unit time, H ' s solution can be used to solve L in polynomial time. As
2120-510: The halting problem by transforming it to the description of a Turing machine that tries all truth value assignments and when it finds one that satisfies the formula it halts and otherwise it goes into an infinite loop. It is also easy to see that the halting problem is not in NP since all problems in NP are decidable in a finite number of operations, but the halting problem, in general, is undecidable . There are also NP-hard problems that are neither NP-complete nor Undecidable . For instance,
2173-407: The machine into an accepting state. When simulating the many branching paths of an NTM on a deterministic machine, we can stop the entire simulation as soon as any branch reaches an accepting state. As a mathematical construction used primarily in proofs, there are a variety of minor variations on the definition of an NTM, but these variations all accept equivalent languages. The head movement in
NP-completeness - Misplaced Pages Continue
2226-573: The most famous unresolved question in computer science, concerns one case of this issue: whether or not every problem solvable by a NTM in polynomial time is necessarily also solvable by a DTM in polynomial time. An NTM has the property of bounded nondeterminism. That is, if an NTM always halts on a given input tape T then it halts in a bounded number of steps, and therefore can only have a bounded number of possible configurations. Because quantum computers use quantum bits , which can be in superpositions of states, rather than conventional bits, there
2279-434: The other. 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 great unsolved problems of mathematics . The Clay 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. The existence of NP-complete problems
2332-408: The output of the transition relation is often encoded numerically instead of using letters to represent moving the head Left (-1), Stationary (0), and Right (+1); giving a transition function output of ( Q × Σ × { − 1 , 0 , + 1 } ) {\displaystyle \left(Q\times \Sigma \times \{-1,0,+1\}\right)} . It
2385-458: The possible computations are all prefixes of a single, possibly infinite, path.) The input for an NTM is provided in the same manner as for a deterministic Turing machine: the machine is started in the configuration in which the tape head is on the first character of the string (if any), and the tape is all blank otherwise. An NTM accepts an input string if and only if at least one of the possible computational paths starting from that string puts
2438-475: The results of a poll he had conducted of the theoretical computer science community. Other suggestions made in the poll 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 the P versus NP problem went, could stand for "provably exponential time" or "previously exponential time". The following misconceptions are frequent. Viewing
2491-428: The set of all decision 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 a non-deterministic Turing machine . A problem p in NP is NP-complete if every other problem in NP can be transformed (or reduced) into p in polynomial time. It is not known whether every problem in NP can be quickly solved—this
2544-405: 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 the logarithmic-space many-one reduction which
2597-492: The tape in state 3 might make the DTM write a Y on the tape, move the head one position to the right, and switch to state 5. In contrast to a deterministic Turing machine, in a nondeterministic Turing machine ( NTM ) the set of rules may prescribe more than one action to be performed for any given situation. For example, an X on the tape in state 3 might allow the NTM to: or How does the NTM "know" which of these actions it should take? There are two ways of looking at it. One
2650-402: The transition relation defines multiple continuations. Another construction simulates NTMs with 3-tape DTMs, of which the first tape always holds the original input string, the second is used to simulate a particular computation of the NTM, and the third encodes a path in the NTM's computation tree. The 3-tape DTMs are easily simulated with a normal single-tape DTM. In the second construction,
2703-401: The tree halts with an "accept" condition, the NTM accepts the input. A nondeterministic Turing machine can be formally defined as a six-tuple M = ( Q , Σ , ι , ⊔ , A , δ ) {\displaystyle M=(Q,\Sigma ,\iota ,\sqcup ,A,\delta )} , where The difference with a standard (deterministic) Turing machine
SECTION 50
#17328834944852756-401: The whole search. " Complete " refers to the property of being able to simulate everything in the same complexity 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 (in polynomial time ), such that the output for any input is "yes" if the solution set is non-empty and "no" if it
2809-422: Was a fierce debate between the computer scientists about whether NP-complete problems could be solved in polynomial time on a deterministic Turing 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
#484515