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. "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)
Van het eerste van deze problemen, het vervulbaarheidsprobleem, had Stephen Cook van de universiteit van Toronto in 1971 de NP-volledigheid aangetoond. "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. 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:
SATISFIABILITY - vervulbaarheidsprobleem 0-1 INTEGER PROGRAMMING - zie Geheeltallige programmering CLIQUE - Clique SET PACKING- Set packing NODE COVER - Knopenbedekking SET COVERING - Verzamelingenoverdekking FEEDBACK NODE SET - Feedback node set FEEDBACK ARC SET - Feedback arc set DIRECTED HAMILTON CIRCUIT - Hamiltonpad UNDIRECTED HAMILTON CIRCUIT- Hamiltonpad SATISFIABILITY WITH AT MOST 3 LITERALS PER CLAUSE - 3-SAT CHROMATIC NUMBER - Chromatisch getal CLIQUE COVER - Clique EXACT COVER - Exacte overdekking HITTING SET - Hitting set STEINER TREE - Steinerboomprobleem 3-DIMENSIONAL MATCHING - driedimensionale koppeling KNAPSACK - Knapzakprobleem JOB SEQUENCING - Job sequencing PARTITION - Partitieprobleem MAX CUT - Maximale snede
Categorie:NP-volledig probleem