Список Карпа — список из 21 NP-полных задач, опубликованный Ричардом Карпом в 1972 году в работе «Сводимость комбинаторных задач» , в которой приведены как формулировки, так и доказательства 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 )

См. также

Примечания