21 NP-повна задача Карпа

Список Карпа — список, що складається з формулювання та доведення NP-повноти 21 задачі, опублікований Річардом Карпом у 1972 році у своїй праці «Зводимість між комбінаторними задачами» (англ. «Reducibility Among Combinatorial Problems»)^[1].

Список задач

• Задача здійсненності бульових формул (англ. SAT)
  • Бінарне цілочисельне програмування (англ. 1-0 integer programming)
  • Задача про кліку (англ. Clique)
    • Задача "пакування" множини (англ. Set packing)
    • Задача про вершинне покриття (англ. Vertex Cover)
      • Задача про покриття множини (англ. Set Covering)
      • Множина вершин, що розрізають контури (англ. Feedback Vertex Set)
      • Множина дуг, що розрізають контури (англ. Feedback Arc Set)
        • Задача пошуку орієнтованого гамільтонова цикла (англ. Hamiltonian path problem, у визначені Карпа — англ. Directed Hamilton Circuit)
        • Задача пошуку неорієнтованого гамільтонова цикла (англ. Hamiltonian path problem, у визначені Карпа — англ. Undirected Hamilton Circuit)
  • Задача здійсненності булевих формул з трьома літералами (англ. 3-SAT)
    • Задача розфарбування графу (англ. Graph coloring)
      • Задача про покриття кліки (англ. Clique cover)
      • Задача про точне покриття (англ. Exact cover)
        • Задача про вершинне покриття у гіперграфах (англ. Vertex cover in hypergraphs)
        • Задача дерева Штайнера (англ. Steiner tree problem)
        • Тривимірне паросполучення (англ. 3-dimensional matching)
        • Задача пакування рюкзака (англ. Knapsack problem)
          • Складання розкладу на одній машині для робіт з кінцевими строками та критерієм мінімуму штрафу (англ. Job sequencing)
          • Проблема розбиття (англ. Partition problem)
            • Задача про максимальний розріз (англ. Maximum cut)

Див. також

• Список NP-повних задач