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 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:

# 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
Q21198
computerwetenschap
Concept
Q131476
grafentheorie
Concept
Q76592
combinatoriek
Concept
Q92612
Richard Karp
PER
Q168756
Universiteit van Californië - Berkeley
LOC
Q23927052
paper
Concept
Q215206
NP-volledig
MISC
Q875276
vervulbaarheidsprobleem
Concept
Q62870
Stephen Cook
PER
Q180865
universiteit van Toronto
LOC
Q875276
vervulbaarheidsprobleem
Concept
Q6042592
Geheeltallige programmering
Concept
Q761631
Clique
Concept
None
Set packing
UNK
Q11515519
Knopenbedekking
Concept
Q1192100
Verzamelingenoverdekking
Concept
None
Feedback node set
UNK
None
Feedback arc set
UNK
Q273037
Hamiltonpad
Concept
Q273037
Hamiltonpad
Concept
None
3-SAT
UNK
None
Chromatisch getal
UNK
Q761631
Clique
Concept
Q388260
Exacte overdekking
Concept
None
Hitting set
UNK
Q1764144
Steinerboomprobleem
Concept
None
driedimensionale koppeling
UNK
Q864457
Knapzakprobleem
Concept
Q6206757
Job sequencing
Concept
Q1065968
Partitieprobleem
Concept
Q942557
Maximale snede
Concept
Q1734364
Karps 21 NP-volledige problemen
Concept
1971-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
1971
DATE
+21^^http://www.w3.org/2001/XMLSchema#decimal
21
NUMBER
+21^^http://www.w3.org/2001/XMLSchema#decimal
21
NUMBER
+21^^http://www.w3.org/2001/XMLSchema#decimal
21
NUMBER
0^^http://www.w3.org/2001/XMLSchema#decimal
0
NUMBER
-1^^http://www.w3.org/2001/XMLSchema#decimal
-1
NUMBER
+3^^http://www.w3.org/2001/XMLSchema#decimal
3
NUMBER
+3^^http://www.w3.org/2001/XMLSchema#decimal
3
NUMBER
+3^^http://www.w3.org/2001/XMLSchema#decimal
3
NUMBER
named after
named after
quantity
quantity
part of
part of
quantity
part of
educated at
employer