- 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)
- Задача раскраски графа (англ. Graph coloring)
См. также
Список NP-полных задач
Примечания
- ↑ «Reducibility Among Combinatorial Problems», Р. Карп, 1972 год (англ.)
Категория:- NP-полные задачи
- Задача выполнимости булевых формул (англ. SAT)
Wikimedia Foundation. 2010.