Karp's 21 NP-complete problems

Karp's 21 NP-complete problems

One of the most important results in computational complexity theory was Stephen Cook's 1971 demonstration of the first (practically relevant) NP-complete problem, the boolean satisfiability problem. [cite book|author = Stephen Cook|year = 1971|chapter = [http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=805047 The Complexity of Theorem Proving Procedures] |title = Proceedings of the third annual ACM symposium on Theory of computing|pages = 151–158] In 1972, Richard Karp took this idea a leap forward with his landmark paper, "Reducibility Among Combinatorial Problems", in which he showed that 21 diverse combinatorial and graph theoretical problems, each infamous for its computational intractability, are NP-complete. [cite book | author = Richard M. Karp | chapter = [http://www.cs.berkeley.edu/~luca/cs172/karp.pdf Reducibility Among Combinatorial Problems] | title = Complexity of Computer Computations | editor = R. E. Miller and J. W. Thatcher (editors) | publisher = New York: Plenum | pages = 85–103 | year = 1972]

By revealing that a large number of problems important to researchers are NP-complete, Karp motivated the study of NP, NP-completeness, and the now-famous P = NP question.

The problems

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

* SAT: the boolean satisfiability problem for formulas in conjunctive normal form
** 0-1 INTEGER PROGRAMMING
** CLIQUE (see also independent set problem)
*** SET PACKING
*** VERTEX COVER
**** SET COVERING
**** FEEDBACK NODE SET
**** FEEDBACK ARC SET
**** DIRECTED HAMILTONIAN CIRCUIT
***** UNDIRECTED HAMILTONIAN CIRCUIT
** 3-SAT
*** CHROMATIC NUMBER (also called the Graph Coloring Problem)
**** CLIQUE COVER
**** EXACT COVER
***** HITTING SET
***** STEINER TREE
***** 3-dimensional MATCHING
***** KNAPSACK (Karp's definition of Knapsack is closer to Subset sum)
****** JOB SEQUENCING
****** PARTITION
******* MAX-CUT

As time went on it was discovered that many of the problems can be solved 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. [cite journal | author = David Zuckerman | 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]

See also

* List of NP-complete problems

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • List of NP-complete problems — 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 NP complete problems). Most of the problems in this list are taken… …   Wikipedia

  • Karp-Lipton theorem — The Karp–Lipton theorem in complexity theory states that if the boolean satisfiability problem (SAT) can be solved by Boolean circuits with a polynomial number of logic gates, then :Pi 2 , = Sigma 2 , and therefore mathrm{PH} , = Sigma 2 ,.That… …   Wikipedia

  • NP-complete — Euler diagram for P, NP, NP complete, and NP hard set of problems In computational complexity theory, the complexity class NP complete (abbreviated NP C or NPC) is a class of decision problems. A decision problem L is NP complete if it is in the… …   Wikipedia

  • Lista de 21 problemas NP-completos de Karp — Por Lista de 21 problemas NP completos de Karp se entiende a una lista de 21 problemas computacionales famosos, que tratan sobre combinatoria y teoría de grafos, y que cumplen la característica en común de que todos ellos pertenecen a la clase de …   Wikipedia Español

  • Permanent is sharp-P-complete — The correct title of this article is Permanent is #P complete. The substitution or omission of the # sign is because of technical restrictions. In a 1979 paper Leslie Valiant proved[1] that the problem of computing the permanent of a matrix is #P …   Wikipedia

  • Richard Karp — Infobox Scientist name = Richard Manning Karp image width = caption = birth date = January 3, 1935 birth place = Boston, Massachusetts death date = death place = residence = citizenship = nationality = American ethnicity = field = Computer… …   Wikipedia

  • Clique problem — The brute force algorithm finds a 4 clique in this 7 vertex graph (the complement of the 7 vertex path graph) by systematically checking all C(7,4)=35 4 vertex subgraphs for completeness. In computer science, the clique problem refers to any of… …   Wikipedia

  • Clique (graph theory) — A graph with 23 1 vertex cliques (its vertices), 42 2 vertex cliques (its edges), 19 3 vertex cliques (the light blue triangles), and 2 4 vertex cliques (dark blue). Six of the edges and 11 of the triangles form maximal cliques. The two dark blue …   Wikipedia

  • Vertex cover — In the mathematical discipline of graph theory, a vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. The problem of finding a minimum vertex cover is a classical… …   Wikipedia

  • Boolean satisfiability problem — For the concept in mathematical logic, see Satisfiability. 3SAT redirects here. For the Central European television network, see 3sat. In computer science, satisfiability (often written in all capitals or abbreviated SAT) is the problem of… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”