Karp's 21 NP-complete problems

One of the most important results of complexity theory is the service rendered by Stephen Cook in 1971 prove that the satisfiability problem of propositional logic is (usually only briefly mentioned SAT) is NP-complete.

1972 attacked Richard Karp to this idea and showed 21 different combinatorial and graph-theoretical problems that were known to them stubbornly deprived of an efficient algorithmic solvability that these are also NP -complete.

By showing that a large number of significant problems are NP-complete, Karp motivated further research into the class NP, the theory of NP- completeness as well as the question whether the classes P and NP are identical or different (P -NP problem). The latter is now one of the most important open mathematical questions. Among other things, it is one of the seven Millennium Problems of the Clay Mathematics Institute for the solution of prizes were awarded of one million U.S. dollars.

List of Issues

The following tree shows Karp's 21 problems, including the associated reduction, which he used to prove their NP- completeness. For example, the NP- completeness of the knapsack problem was demonstrated by the problem of the exact coverage was reduced to.

  • Satisfiability: the satisfiability of propositional logic formulas in conjunctive normal form for CLIQUE: clique problem SET PACKING: Quantity packing problem
  • VERTEX COVER: vertex cover problem SET COVERING: Quantity cover problem
  • FEEDBACK ARC SET: Feedback Arc Set
  • NODE SET FEEDBACK: Feedback Vertex Set
  • DIRECTED Hamiltonian CIRCUIT: see Hamilton cycle problem Undirected Hamiltonian CIRCUIT: see Hamilton cycle problem
  • CHROMATIC NUMBER: graph coloring problem- CLIQUE COVER: Covering by Cliques
  • EXACT COVER: problem of exact registration 3- dimensional MATCHING: 3- dimensional matching (Stable Marriage with three genders )
  • STEINER TREE: Steiner tree problem
  • HITTING SET: Hitting Set Problem
  • KNAPSACK: knapsack problem JOB SEQUENCING: sequencing Job
  • PARTITION: partition problem MAX -CUT: Maximum average
Richard M. Karp Boolean satisfiability problem#3-satisfiability Vertex cover#Vertex cover in hypergraphs Maximum cut
467080
de