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)
- Задача розфарбування графу (англ. Graph coloring)
Див. також
- Список NP-повних задач
Посилання
- «Reducibility Among Combinatorial Problems», Р. Карп, 1972 рік (англ.)
Джерела
- 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. У 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.