Karps 21 NP-volledige problemen

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Karps 21 NP-volledige problemen zijn 21 problemen uit de theoretische computerwetenschap, hoofdzakelijk op het gebied van grafentheorie en combinatoriek, waarvan Richard Karp van de Universiteit van Californië - Berkeley in een paper uit 1972 aantoonde dat ze NP-volledig zijn.[1]

Van het eerste van deze problemen, het vervulbaarheidsprobleem, had Stephen Cook van de universiteit van Toronto in 1971 de NP-volledigheid aangetoond.[2] Karp steunde hierop en bewees dat elk van de andere problemen kan gereduceerd worden tot het vervulbaarheidsprobleem en er dus mee equivalent is.

De 21 problemen, met de benamingen die Karp ervoor gebruikte, zijn:

  1. SATISFIABILITY - vervulbaarheidsprobleem
  2. 0-1 INTEGER PROGRAMMING - zie Geheeltallige programmering
  3. CLIQUE - Clique
  4. SET PACKING- Set packing
  5. NODE COVER - Knopenbedekking
  6. SET COVERING - Verzamelingenoverdekking
  7. FEEDBACK NODE SET - Feedback node set
  8. FEEDBACK ARC SET - Feedback arc set
  9. DIRECTED HAMILTON CIRCUIT - Hamiltonpad
  10. UNDIRECTED HAMILTON CIRCUIT- Hamiltonpad
  11. SATISFIABILITY WITH AT MOST 3 LITERALS PER CLAUSE - 3-SAT
  12. CHROMATIC NUMBER - Chromatisch getal
  13. CLIQUE COVER - Clique
  14. EXACT COVER - Exacte overdekking
  15. HITTING SET - Hitting set
  16. STEINER TREE - Steinerboomprobleem
  17. 3-DIMENSIONAL MATCHING - driedimensionale koppeling
  18. KNAPSACK - Knapzakprobleem
  19. JOB SEQUENCING - Job sequencing
  20. PARTITION - Partitieprobleem
  21. MAX CUT - Maximale snede
Bronnen, noten en/of referenties
  1. Richard M. Karp. "Reducibility Among Combinatorial Problems". In: Raymond E. Miller, James W. Thatcher (Eds.): Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York. Plenum Press, New York 1972 (blz. 85-103)
  2. Stephen A. Cook. "The Complexity of Theorem-Proving Procedures." In: STOC '71 Proceedings of the third annual ACM symposium on Theory of computing. ACM, 1971, blz. 151-158