21 NP-komplett Karp-problem

Karps lista är en lista som består av formuleringen och beviset på NP-fullständighet av 21 problem, publicerad av Richard Karp 1972 i hans verk Reducibility Among Combinatorial Problems [1 ] . 

Uppgiftslista

• Boolesk formeltillfredsställelseproblem ( SAT ) 
  • Binär heltalsprogrammering ( eng.  1-0 heltalsprogrammering )
  • Klickproblem _ _  _ _
    • Ställ in packningsproblem _ _ 
    • Vertex Cover Problem _ _ 
      • Ställ in täckningsproblem  _ _
      • Problemet med en slingklippande uppsättning av hörn ( eng.  Feedback Vertex Set )
      • Feedback
      Arc Set  Problem _
      • Riktat Hamiltonskt grafproblem _ _ _ _ _ _  
      • Oriktat
      Hamiltonsk grafproblem _ _  _ _ _ _ 

Se även

Lista över NP-kompletta problem

Anteckningar

1. ↑ "Reducibility Among Combinatorial Problems" Arkiverad 29 juni 2011 på Wayback Machine , R. Karp , 1972