21 NP-úplný Karp problém

Karpův seznam je seznam sestávající z formulace a důkazu NP-úplnosti 21 problémů, publikovaný Richardem Karpem v roce 1972 ve své práci Reducibility Among Combinatorial Problems [1 ] . 

Seznam úkolů

• Problém splnitelnosti booleovských vzorců ( SAT ) 
  • Binární celočíselné programování ( eng.  1-0 celočíselné programování )
  • Problém s klikáním _ _  _
    • Nastavit problém s balením _ _ 
    • Problém krytu vertexu _ _ 
      • Nastavit
      problém krytí _ _ 
    • Problém smyčkového řezání množiny vrcholů ( eng.  Feedback Vertex Set )
    • Zpětná vazba
    Problém s nastavením  oblouku _
    • Problém s řízeným hamiltonovským grafem _ _  _ _ _ 
    • Problém neorientovaného hamiltonovského grafu _ _  _ _ _ 

Viz také

Seznam NP-úplných problémů

Poznámky

1. ↑ „Redukovatelnost mezi kombinatorickými problémy“ Archivováno 29. června 2011 na Wayback Machine , R. Karp , 1972