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» [Архівовано 29 червня 2011 у Wayback Machine.], Р. Карп, 1972 рік (англ.)
Джерела
- Stephen Cook (1971). The Complexity of Theorem Proving Procedures. Proceedings of the third annual ACM symposium on Theory of computing. с. 151—158. Архів оригіналу за 6 серпня 2020. Процитовано 5 вересня 2017.
- 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. Архів оригіналу (PDF) за 10 лютого 2021. Процитовано 5 вересня 2017.
- Zuckerman, David (1996). On Unapproximable Versions of NP-Complete Problems. SIAM Journal on Computing. 25 (6): 1293—1304. doi:10.1137/S0097539794266407. Архів оригіналу за 11 серпня 2006. Процитовано 5 вересня 2017. [1]
- п
- о
- р
NP-повні задачі
Дослідження операцій:Оптимізація:Комбінаторна оптимізація
Задача заміщення сторінок · Задача здійсненності бульових формул · Задача комівояжера · Задача листоноші · Задача пакування рюкзака · Задача про кліку · Задача про точне покриття · Задача про пакування в ємності (двомірне пакування • лінійне пакування тощо) • Задача Штейнера • Задача про вершинне покриття • Задача про незалежну множину • Задача про покриття множини · ...
та головоломки
Гра в п'ятнашки (гра в N2-1) (Задача пошуку найкоротшого рішення) • Задачі, рішення яких застосовуються в Тетрисі • Задача узагальненого судоку • Задача про заповнення латинського квадрата • Задачі какуро
21 NP-повна задача Карпа · Список NP-повних задач