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