Karps 21 NP-volledige problemen

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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:

  1. SATISFIABILITY - vervulbaarheidsprobleem
  2. 0-1 INTEGER PROGRAMMING - zie Geheeltallige programmering
  3. CLIQUE - Clique
  4. SET PACKING- Set packing
  5. NODE COVER - Knopenbedekking
  6. SET COVERING - Verzamelingenoverdekking
  7. FEEDBACK NODE SET - Feedback node set
  8. FEEDBACK ARC SET - Feedback arc set
  9. DIRECTED HAMILTON CIRCUIT - Hamiltonpad
  10. UNDIRECTED HAMILTON CIRCUIT- Hamiltonpad
  11. SATISFIABILITY WITH AT MOST 3 LITERALS PER CLAUSE - 3-SAT
  12. CHROMATIC NUMBER - Chromatisch getal
  13. CLIQUE COVER - Clique
  14. EXACT COVER - Exacte overdekking
  15. HITTING SET - Hitting set
  16. STEINER TREE - Steinerboomprobleem
  17. 3-DIMENSIONAL MATCHING - driedimensionale koppeling
  18. KNAPSACK - Knapzakprobleem
  19. JOB SEQUENCING - Job sequencing
  20. PARTITION - Partitieprobleem
  21. MAX CUT - Maximale snede