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:
- 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
Bronnen, noten en/of referenties
|