21 NP-teljes Karp probléma

Karp listája egy lista, amely 21 probléma NP-teljességének megfogalmazását és bizonyítását tartalmazza , Richard Karp 1972-ben publikálta Reducibility among Combinatorial Problems [1 ] című munkájában . 

Feladatlista

• Boole-képlet kielégítési problémája ( SAT ) 
  • Bináris egész számok programozása ( eng.  1-0 integer programozás )
  • Klikk probléma _ _  _
    • Csomagolási
    probléma beállítása _ _ 
  • Csúcs fedő probléma _ _ 
    • Lefedési probléma beállítása _ _ 
    • A csúcsok hurokvágó halmazának problémája ( eng.  Feedback Vertex Set )
    • Visszacsatolási ívkészlet  probléma _ _
      • Irányított Hamilton- gráf probléma _ _  _
      _ _ 
    • Irányítatlan
    Hamilton - gráf probléma _ _  _ _ _ 

Lásd még

Az NP-teljes problémák listája

Jegyzetek

1. ↑ "Csökkenthetőség a kombinatorikus problémák között" archiválva : 2011. június 29., a Wayback Machine , R. Karp , 1972