Karps 21 NP-volledige problemen

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 het vervulbaarheidsprobleem tot elk van de andere problemen polynomiaal gereduceerd kan worden, en daarmee dat die problemen ook NP-volledig zijn.

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. Gearchiveerd op 2 maart 2014.