Список Карпа — список, що складається з формулювання та доведення 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)
- Задача розфарбування графу (англ. Graph coloring)
Див. також
Посилання
- «Reducibility Among Combinatorial Problems» [ 29 червня 2011 у Wayback Machine.], Р. Карп, 1972 рік (англ.)
Джерела
- Stephen Cook (1971). . Proceedings of the third annual ACM symposium on Theory of computing. с. 151—158. Архів оригіналу за 6 серпня 2020. Процитовано 5 вересня 2017.
- Richard M. Karp (1972). (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). . SIAM Journal on Computing. 25 (6): 1293—1304. doi:10.1137/S0097539794266407. Архів оригіналу за 11 серпня 2006. Процитовано 5 вересня 2017.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет