Karps 21 NP-volledige problemen
Uiterlijk
(Doorverwezen vanaf 21 NP-compleet problemen van Karp)
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
- ↑ 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)
- ↑ 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.