Список Карпа

Список Карпа — список из 21 NP-полных задач, опубликованный Ричардом Карпом в 1972 году в работе «Сводимость комбинаторных задач»^[1], в которой приведены как формулировки, так и доказательства NP-полноты для каждой:

• задача выполнимости булевых формул (англ. 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-полных задач^[англ.]