Список Карпа - список, состоящий из формулировки и доказательства 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)

См. также

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

Примечания