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 год (англ.)
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.