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

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

Список задач

• Задача здійсненності бульових формул (англ. 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-повних задач

Джерела

• Stephen Cook (1971). The Complexity of Theorem Proving Procedures. Proceedings of the third annual ACM symposium on Theory of computing. с. 151—158.
• Richard M. Karp (1972). Reducibility Among Combinatorial Problems (PDF). У R. E. Miller and J. W. Thatcher (editors) (ред.). Complexity of Computer Computations. New York: Plenum. с. 85—103.
• Zuckerman, David (1996). On Unapproximable Versions of NP-Complete Problems. SIAM Journal on Computing. 25 (6): 1293—1304. doi:10.1137/S0097539794266407. [1]