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.

Van het eerste van deze problemen, het vervulbaarheidsprobleem, had Stephen Cook van de universiteit van Toronto in 1971 de NP-volledigheid aangetoond. 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

NP-volledig probleem