21 NP-полная задача Карпа

Список Карпа — список, состоящий из формулировки и доказательства 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)
          • Теория расписаний (англ. Job sequencing)
          • Задача разбиения множества чисел (англ. Partition problem)
          • Максимальный разрез графа (англ. Maximum cut)

См. также

Список NP-полных задач