In computational complexity theory, the complexity class NP-complete, also known as NP-C or NPC, is a subset of NP, the set of all decision problems whose solutions can be verified quickly. Computational complexity theory, as a branch of the Theory of computation in Computer science, investigates the problems related to the amounts of resources In Computational complexity theory, a complexity class is a set of problems of related complexity In Computational complexity theory, NP is one of the most fundamental Complexity classes The abbreviation NP refers to " N on-deterministic In Computability theory and Computational complexity theory, a decision problem is a question in some Formal system with a yes-or-no answer depending on A problem p in NP is also in NPC if and only if every other problem in NP can be quickly turned into a problem within p. ↔ (The word "quickly" in those statements refers to polynomial time; a more formal definition of NP-complete is given below. ) NP-complete can also be used as an adjective: problems in NP-complete are known as NP-complete problems. In Grammar, an adjective is a word whose main syntactic role is to modify a Noun or Pronoun, giving more information about the

NP-complete problems are studied because the ability to quickly verify solutions to a problem (NP) seems to correlate with the ability to quickly solve that problem (P). In Computational complexity theory, P, also known as PTIME or DTIME ( n O(1 is one of the most fundamental Complexity It is not known whether every problem in NP can be quickly solved -- this is called the P = NP problem. The relationship between the Complexity classes P and NP is an unsolved question in Theoretical computer science. But if any single problem in NP-complete can be solved quickly, then every problem in NP can also be quickly solved, because the definition of an NP-complete problem states that every problem in NP must be quickly reducible to every problem in NP-complete. Because of this, it is often said that the NP-complete problems are "harder" or "more difficult" than NP problems in general.

Formal definition of NP-completeness

A decision problem C is NP-complete if:

1. C is in NP, and
2. Every problem in NP is reducible to C. In Computability theory and Computational complexity theory, a decision problem is a question in some Formal system with a yes-or-no answer depending on In Computational complexity theory, NP is one of the most fundamental Complexity classes The abbreviation NP refers to " N on-deterministic In Computational complexity theory, NP is one of the most fundamental Complexity classes The abbreviation NP refers to " N on-deterministic In Computability theory and Computational complexity theory, a reduction is a transformation of one problem into another problem

C can be shown to be in NP by demonstrating that a candidate solution to C can be verified in polynomial time. In Computational complexity theory, NP is one of the most fundamental Complexity classes The abbreviation NP refers to " N on-deterministic

A problem K is reducible to C if there is a polynomial-time many-one reduction, a deterministic algorithm which transforms instances k ∈ K into instances c ∈ C, such that the answer to c is YES if and only if the answer to k is YES. In Computational complexity theory a polynomial-time reduction is a reduction which is computable by a Deterministic Turing machine in Polynomial time In Computer science, a deterministic algorithm is an Algorithm which in informal terms behaves predictably ↔ To prove that an NP problem A is in fact an NP-complete problem it is sufficient to show that an already known NP-complete problem reduces to A.

Note that a problem satisfying condition 2 is said to be NP-hard, whether or not it satisfies condition 1. NP-hard (nondeterministic Polynomial-time hard in Computational complexity theory, is a class of problems informally "at least as hard as the hardest problems

A consequence of this definition is that if we had a polynomial time algorithm (on a UTM, or any other Turing-equivalent abstract machine) for C, we could solve all problems in NP in polynomial time. This article is a supplement to the article Turing machine. Alan Turing 's "universal computing machine" (alternately "universal An abstract machine, also called an abstract computer, is a theoretical model of a Computer hardware or software system used in Automata theory.

A more detailed formal definition of NP-completeness can be found here. The relationship between the Complexity classes P and NP is an unsolved question in Theoretical computer science.

Background

The concept of "NP-complete" was introduced by Stephen Cook in a paper entitled 'The complexity of theorem-proving procedures' on pages 151-158 of the Proceedings of the 3rd Annual ACM Symposium on Theory of Computing in 1971, though the term "NP-complete" did not appear anywhere in his paper. Stephen Arthur Cook (born December 14, 1939, Buffalo, New York) is a noted computer scientist. In general usage complexity often tends to be used to characterize something with many parts in intricate arrangement At that computer science conference, there was a fierce debate among the computer scientists about whether NP-complete problems could be solved in polynomial time on a deterministic Turing machine. Computer science (or computing science) is the study and the Science of the theoretical foundations of Information and Computation and their Determinism is the philosophical Proposition that every event including human cognition and behaviour decision and action is causally determined Turing machines are basic abstract symbol-manipulating devices which despite their simplicity can be adapted to simulate the logic of any Computer Algorithm 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. John Edward Hopcroft (born October 7, 1939) is a renowned theoretical Computer scientist. This is known as the question of whether P=NP. The relationship between the Complexity classes P and NP is an unsolved question in Theoretical computer science.

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. In Computational complexity theory, the Complexity class NP-complete (abbreviated NP-C or NPC) is a class of problems having two properties This article lists some unsolved problems in Mathematics. See individual articles for details and sources The Clay Mathematics Institute is offering a $1 million reward to anyone who has a formal proof that P=NP or that P≠NP. The Clay Mathematics Institute (CMI is a private Non-profit foundation, based in Cambridge, Massachusetts.

In the celebrated Cook-Levin theorem (independently proved by Leonid Levin), Cook proved that the Boolean satisfiability problem is NP-complete (a simpler, but still highly technical proof of this is available). In Computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete Leonid Anatolievich Levin (לאוניד אנטולייביץ לוין Леонид Анатольевич Левин born November In Computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete 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). Richard Manning Karp (born 1935 is a Computer scientist and Computational theorist, notable for research in One of the most important results in Computational complexity theory was Stephen Cook 's 1971 demonstration of the first (practically relevant NP-complete problem 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's 1979 book Computers and Intractability: A Guide to NP-Completeness. David Stifler Johnson (born December 9, 1945) is a Computer scientist specializing in Algorithms and optimization

NP-complete problems

Main article: List of NP-complete problems

Some NP-complete problems, indicating the reductions typically used to prove their NP-completeness

An interesting example is the graph isomorphism problem, the graph theory problem of determining whether a graph isomorphism exists between two graphs. Here are some of the more commonly known problems that are NP-complete when expressed as Decision problems This list is in no way comprehensive (there are more than 3000 known In Computability theory and Computational complexity theory, a reduction is a transformation of one problem into another problem In Graph theory, an isomorphism of graphs G and H is a Bijection between the vertex sets of G and H In Mathematics and Computer science, graph theory is the study of graphs: mathematical structures used to model pairwise relations between objects In Graph theory, an isomorphism of graphs G and H is a Bijection between the vertex sets of G and H In Mathematics and Computer science, a graph is the basic object of study in Graph theory. Two graphs are isomorphic if one can be transformed into the other simply by renaming vertices. In Mathematics and Computer science, a graph is the basic object of study in Graph theory. In Abstract algebra, an isomorphism ( Greek: ἴσος isos "equal" and μορφή morphe "shape" is a bijective In Abstract algebra, an isomorphism ( Greek: ἴσος isos "equal" and μορφή morphe "shape" is a bijective For other uses see Vertex. In Graph theory, a vertex (plural vertices) or node is the fundamental unit out Consider these two problems:

• Graph Isomorphism: Is graph G₁ isomorphic to graph G₂?
• Subgraph Isomorphism: Is graph G₁ isomorphic to a subgraph of graph G₂?

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. In Graph theory, an isomorphism of graphs G and H is a Bijection between the vertex sets of G and H 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. The list below contains some well-known problems that are NP-complete when expressed as decision problems. In Computability theory and Computational complexity theory, a decision problem is a question in some Formal system with a yes-or-no answer depending on

To the right is a diagram of some of the problems and the reductions typically used to prove their NP-completeness. The n -puzzle is known in various versions including the 8 puzzle, the 15 puzzle, and with various names The knapsack problem is a problem in Combinatorial optimization. In the mathematical field of Graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian The Travelling salesman problem ( TSP) in Operations research is a problem in discrete or Combinatorial optimization. In complexity theory, Subgraph-Isomorphism is a Decision problem that is known to be NP-complete. In Computer science, the subset sum problem is an important problem in complexity theory and Cryptography. In Computational complexity theory, the clique problem is a graph-theoretic NP-complete problem In Computer science, the vertex cover problem or node cover problem is an NP-complete problem and was one of Karp's 21 NP-complete problems. In Mathematics, the independent set problem ( IS) is a well-known problem in Graph theory and Combinatorics. In Graph theory, graph coloring is a special case of Graph labeling; it is an assignment of labels traditionally called "colors" to elements of a In Computability theory and Computational complexity theory, a reduction is a transformation of one problem into another problem 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.

There is often only a small difference between a problem in P and an NP-complete problem. For example, the 3SAT problem, a restriction of the boolean satisfiability problem, remains NP-complete, whereas the slightly more restricted 2SAT problem is in P (specifically, NL-complete), and the slightly more general MAX 2SAT problem is again NP-complete. In Computer science, 2-satisfiability (abbreviated as 2-SAT is the problem of determining whether a collection of two-valued ( Boolean or binary) variables In Computational complexity theory, NL-Complete is a Complexity class which is complete for NL. 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. Kuratowski's and Wagner's theorems The Polish mathematician Kazimierz Kuratowski provided a characterization of planar graphs in terms of Forbidden Determining if a graph is a cycle or is bipartite is very easy (in L), but finding a maximum bipartite or a maximum cycle subgraph is NP-complete. In Graph theory, a cycle graph is a graph that consists of a single cycle, or in other words some number of vertices connected in a closed chain In the mathematical field of Graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two In Computational complexity theory, L is the Complexity class containing Decision problems which can be solved by a Deterministic Turing machine 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. The knapsack problem is a problem in Combinatorial optimization.

Solving NP-complete problems

At present, all known algorithms for NP-complete problems require time that is superpolynomial in the input size, and it is unknown whether there are any faster algorithms. In Mathematics, Computing, Linguistics and related subjects an algorithm is a sequence of finite instructions often used for Calculation

The following techniques can be applied to solve computational problems in general, and they often give rise to substantially faster algorithms:

• Approximation: Instead of searching for an optimal solution, search for an "almost" optimal one. In Computer science and Operations research, approximation algorithms are Algorithms used to find approximate solutions to Optimization problems
• Randomization: Use randomness to get a faster average running time, and allow the algorithm to fail with some small probability. A randomized algorithm or probabilistic algorithm is an Algorithm which employs a degree of randomness as part of its logic To analyze an Algorithm is to determine the amount of resources (such as time and storage necessary to execute it
• Restriction: By restricting the structure of the input (e. g. , to planar graphs), faster algorithms are usually possible. Kuratowski's and Wagner's theorems The Polish mathematician Kazimierz Kuratowski provided a characterization of planar graphs in terms of Forbidden
• Parameterization: Often there are fast algorithms if certain parameters of the input are fixed. In Computer science, parameterized complexity is a measure of complexity of problems with multiple input parameters
• Heuristic: An algorithm that works "reasonably well" on many cases, but for which there is no proof that it is both always fast and always produces a good result. In Computer science, a heuristic algorithm or simply a Heuristic is an Algorithm that ignores whether the solution to the problem can be proven Metaheuristic approaches are often used. A metaheuristic is a Heuristic method for solving a very general class of computational problems by combining user-given black-box procedures ��usually heuristics

One example of a heuristic algorithm is a suboptimal O(n log n) greedy algorithm used for graph coloring during the register allocation phase of some compilers, a technique called graph-coloring global register allocation. A greedy algorithm is any Algorithm that follows the Problem solving Metaheuristic of making the locally optimum choice at each stagewith the hope In Graph theory, graph coloring is a special case of Graph labeling; it is an assignment of labels traditionally called "colors" to elements of a In Compiler optimization, register allocation is the process of Multiplexing a large number of target program Variables onto a small number of 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.

Completeness under different types of reduction

In the definition of NP-complete given above, the term "reduction" was used in the technical meaning of a polynomial-time many-one reduction. In Computational complexity theory a polynomial-time reduction is a reduction which is computable by a Deterministic Turing machine in Polynomial time

Another type of reduction is polynomial-time Turing reduction. In Computational complexity theory a polynomial-time reduction is a reduction which is computable by a Deterministic Turing machine in Polynomial time A problem X is polynomial-time Turing-reducible to a problem Y if, given a subroutine that solves Y in polynomial time, one 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. In Computational complexity theory, co-NP is a Complexity class. 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 co-NP article. In Computational complexity theory, co-NP is a Complexity class. Although whether 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. In Computational complexity theory, the Complexity class NP-complete (abbreviated NP-C or NPC) is a class of problems having two properties

Another type of reduction that is also often used to define NP-completeness is the logarithmic-space many-one reduction which is a many-one reduction that can be computed with only a logarithmic amount of space. In Computational complexity theory, a log-space reduction is a reduction computable by a Deterministic Turing machine using Logarithmic 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. In Computational complexity theory, L is the Complexity class containing Decision problems which can be solved by a Deterministic Turing machine In Computational complexity theory, a log-space reduction is a reduction computable by a Deterministic Turing machine using Logarithmic space In Computational complexity theory a polynomial-time reduction is a reduction which is computable by a Deterministic Turing machine in Polynomial time 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. In complexity theory, the notion of P-complete Decision problems is useful in the analysis of both which problems are difficult to parallelize effectively Whether under these types of reductions the definition of NP-complete changes is still an open problem.

See also

• List of NP-complete problems
• Almost complete
• Ladner's theorem
• Strongly NP-complete
• P = NP problem

References

• Garey, M. and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979. Here are some of the more commonly known problems that are NP-complete when expressed as Decision problems This list is in no way comprehensive (there are more than 3000 known In Computer science, a problem is almost complete for a Complexity class C if it is both in C and "many" other problems in C reduce to it In Computational complexity, Ladner's theorem asserts that if the computational classes P and NP are not equal the latter contains problems that are neither In Computational complexity, strong NP-completeness is a property of computational problems that is a special case of NP-completeness. The relationship between the Complexity classes P and NP is an unsolved question in Theoretical computer science. Michael R Garey is a Computer science researcher and co-author (with David S David Stifler Johnson (born December 9, 1945) is a Computer scientist specializing in Algorithms and optimization Computers and Intractability A Guide to the Theory of NP-Completeness is a Computational complexity theory textbook by Michael Garey and David S ISBN 0-7167-1045-5 (This book is a classic, developing the theory, then cataloguing many NP-Complete problems)
• S. A. Cook (1971). Stephen Arthur Cook (born December 14, 1939, Buffalo, New York) is a noted computer scientist. "The complexity of theorem proving procedures". Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York: 151-158.  
• Paul E. Dunne. An Annotated List of Selected NP-complete Problems. The University of Liverpool, Dept of Computer Science, COMP202. The University of Liverpool is a University in the city of Liverpool, England.
• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, and Gerhard Woeginger. Marek Karpinski is a Computer scientist and Mathematician known for his research in the theory of algorithms and their applications combinatorial A compendium of NP optimization problems. KTH NADA. Stockholm.
• Computational Complexity of Games and Puzzles
• Tetris is Hard, Even to Approximate
• Minesweeper is NP-complete!
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Thomas H Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. Charles Eric Leiserson is a Computer scientist, specializing in the theory of Parallel computing and Distributed computing, and particularly practical Ronald Linn Rivest (born 1947, Schenectady, New York) is a cryptographer. Clifford Stein, a Computer scientist, is currently a professor of Industrial engineering and Operations research at Columbia University Introduction to Algorithms, Second Edition. Introduction to Algorithms is a book by Thomas H Cormen, Charles E MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 34: NP-Completeness, pp. 966–1021.
• Michael Sipser (1997). Michael Fredric Sipser is a Professor of Applied Mathematics in the Theory of Computation Group at the Massachusetts Institute of Technology. Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X.   Sections 7. 4–7. 5 (NP-completeness, Additional NP-complete Problems), pp. 248–271.
• Christos Papadimitriou (1994). Christos Harilaos Papadimitriou (Χρίστος Χαριλάου Παπαδημητρίου is a Professor in the Computer Science Division at the University of California Computational Complexity, 1st edition, Addison Wesley. ISBN 0-201-53082-1.   Chapter 9: NP-complete problems, pp. 181–218.