21 Problemă Karp NP-completă

Lista lui Karp este o listă constând din formularea și demonstrarea completității NP a 21 de probleme, publicată de Richard Karp în 1972 în lucrarea sa Reducibility Among Combinatorial Problems [1 ] . 

Lista de activități

• Problema de satisfacție a formulei booleene ( SAT ) 
  • Programare cu numere întregi binare ( ing.  1-0 programare cu numere întregi )
  • problema clicei _ _  _
    • Setați problema de ambalare _ _ 
    • Problemă acoperire cu vârfuri _ _ 
      • Setați
      problema acoperirii _ _ 
    • Problema unui set de vârfuri de tăiere a buclei ( de exemplu Feedback Vertex  Set )
    • Problema setului  arcului de feedback _
      • Problemă cu graficul hamiltonian direcționat _ _  _ _ _ 
      • Problemă cu graficul hamiltonian nedirecționat _ _  _ _ _ 
• Problemă de satisfacție pentru formulele booleene cu trei literale ( eng.  3-SAT )
  • Problemă de colorare a graficului _ _ 
    • Problemă cu coperta
    clicei _ _ 
  • Problema cu acoperirea exactă ( English  Exact cover )
    • Acoperirea vârfurilor în problema hipergrafelor _ 
    • Problema  minimă a arborelui lui Steiner
    • Problemă de potrivire tridimensională ( eng.  potrivire tridimensională )
    • Problemă la rucsac _ _  _
      • Teoria orarului _ _  _
      • Problemă de partiție _ _  _
      • Tăierea maximă a graficului ( ing.  Tăiere maximă )

Vezi și

Lista problemelor NP-complete

Note

1. ↑ „Reducibility Among Combinatorial Problems” Arhivat 29 iunie 2011 la Wayback Machine , R. Karp , 1972