computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...

, Karp's 21 NP-complete problems are a set of

computational problem In theoretical computer science, a computational problem is one that asks for a solution in terms of an algorithm. For example, the problem of factoring :"Given a positive integer ''n'', find a nontrivial prime factor of ''n''." is a computati ...

s which are

NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

. In his 1972 paper, "Reducibility Among Combinatorial Problems",

Richard Karp Richard Manning Karp (born January 3, 1935) is an American computer scientist and computational theorist at the University of California, Berkeley. He is most notable for his research in the theory of algorithms, for which he received a Turin ...

used

Stephen Cook Stephen Arthur Cook (born December 14, 1939) is an American-Canadian computer scientist and mathematician who has made significant contributions to the fields of complexity theory and proof complexity. He is a university professor emeritus at ...

's 1971 theorem that the

boolean satisfiability problem In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) asks whether there exists an Interpretation (logic), interpretation that Satisf ...

is NP-complete (also called the

Cook–Levin theorem In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-completeness, NP-complete. That is, it is in NP (complexity), NP, and any problem in NP can be reducti ...

) to show that there is a

polynomial time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...

many-one reduction In computability theory and computational complexity theory, a many-one reduction (also called mapping reduction) is a reduction that converts instances of one decision problem (whether an instance is in L_1) to another decision problem (whether ...

from the boolean satisfiability problem to each of 21

combinatorial Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...

and graph theoretical computational problems, thereby showing that they are all NP-complete. This was one of the first demonstrations that many natural computational problems occurring throughout

computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...

are computationally intractable, and it drove interest in the study of NP-completeness and the

P versus NP problem The P versus NP problem is a major unsolved problem in theoretical computer science. Informally, it asks whether every problem whose solution can be quickly verified can also be quickly solved. Here, "quickly" means an algorithm exists that ...

The problems

Karp's 21 problems are shown below, many with their original names. The nesting indicates the direction of the reductions used. For example, Knapsack was shown to be NP-complete by reducing

Exact cover In the mathematical field of combinatorics, given a collection \mathcal of subsets of a set X, an exact cover is a subcollection \mathcal^ of \mathcal such that each element in X is contained in ''exactly one'' subset in \mathcal^. One says that e ...

to Knapsack. *

Satisfiability In mathematical logic, a formula is ''satisfiable'' if it is true under some assignment of values to its variables. For example, the formula x+3=y is satisfiable because it is true when x=3 and y=6, while the formula x+1=x is not satisfiable over ...

: the boolean satisfiability problem for formulas in

conjunctive normal form In Boolean algebra, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals; otherwise put, it is a product of sums or an AND of ORs. In au ...

(often referred to as SAT) ** 0–1 integer programming (A variation in which only the restrictions must be satisfied, with no optimization) **

Clique A clique (AusE, CanE, or ; ), in the social sciences, is a small group of individuals who interact with one another and share similar interests rather than include others. Interacting with cliques is part of normative social development regardles ...

(see also independent set problem) ***

Set packing Set packing is a classical NP-complete problem in computational complexity theory and combinatorics, and was one of Karp's 21 NP-complete problems. Suppose one has a finite set ''S'' and a list of subsets of ''S''. Then, the set packing problem as ...

***

Vertex cover In graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph. In computer science, the problem of finding a minimum vertex cover is a classical optimizat ...

**** Set covering **** Feedback node set **** Feedback arc set **** Directed Hamilton circuit (Karp's name, now usually called Directed Hamiltonian cycle) ***** Undirected Hamilton circuit (Karp's name, now usually called Undirected Hamiltonian cycle) ** Satisfiability with at most 3 literals per clause (equivalent to 3-SAT) ***

Chromatic number In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...

(also called the

Graph Coloring Problem In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...

) **** Clique cover ****

***** Hitting set *****

Steiner tree In combinatorial mathematics, the Steiner tree problem, or minimum Steiner tree problem, named after Jakob Steiner, is an umbrella term for a class of problems in combinatorial optimization. While Steiner tree problems may be formulated in a n ...

*****

3-dimensional matching In the mathematical discipline of graph theory, a 3-dimensional matching is a generalization of bipartite matching (also known as 2-dimensional matching) to 3-partite hypergraphs, which consist of hyperedges each of which contains 3 vertices (ins ...

***** Knapsack (Karp's definition of Knapsack is closer to Subset sum) ****** Job sequencing ****** Partition *******

Max cut In a graph, a maximum cut is a cut whose size is at least the size of any other cut. That is, it is a partition of the graph's vertices into two complementary sets and , such that the number of edges between and is as large as possible. ...

Approximations

As time went on it was discovered that many of the problems can be solved efficiently if restricted to special cases, or can be solved within any fixed percentage of the optimal result. However, David Zuckerman showed in 1996 that every one of these 21 problems has a constrained optimization version that is impossible to approximate within any constant factor unless P = NP, by showing that Karp's approach to reduction generalizes to a specific type of approximability reduction. However, these may be different from the standard optimization versions of the problems, which may have approximation algorithms (as in the case of maximum cut).

Notes

References

* * * {{cite journal , last = Zuckerman , first = David , url = http://citeseer.ist.psu.edu/192662.html , title = On Unapproximable Versions of NP-Complete Problems , journal = SIAM Journal on Computing , volume = 25 , issue = 6 , pages = 1293–1304 , year = 1996 , doi = 10.1137/S0097539794266407 , url-access = subscription }

NP-complete problems, * Mathematics-related lists

The problems

Approximations

See also

Notes

References