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