В теории вычислительной сложности 21 NP-полная задача Карпа представляет собой набор вычислительных задач , которые являются NP-полными . В своей статье 1972 года «Сводимость среди комбинаторных задач» [1] Ричард Карп использовал теорему Стивена Кука 1971 года о том, что проблема булевой выполнимости является NP-полной [2] (также называемую теоремой Кука-Левина ), чтобы показать, что существует полиномиальное по времени сведение к нескольким единицам от проблемы булевой выполнимости к каждой из 21 комбинаторной и теоретико-графовой вычислительной задачи, тем самым показывая, что все они являются NP-полными. Это было одной из первых демонстраций того, что многие естественные вычислительные задачи, встречающиеся в компьютерной науке, являются вычислительно неразрешимыми , и это вызвало интерес к изучению NP-полноты и проблемы P против NP .
Ниже показаны 21 задача Карпа, многие из которых имеют свои оригинальные названия. Вложенность указывает направление используемых сокращений. Например, было показано, что Knapsack является NP-полной задачей путем сведения Exact cover к Knapsack .
Со временем было обнаружено, что многие из проблем могут быть решены эффективно, если ограничиться особыми случаями, или могут быть решены в пределах любого фиксированного процента от оптимального результата. Однако Дэвид Цукерман показал в 1996 году, что каждая из этих 21 проблем имеет версию ограниченной оптимизации, которую невозможно аппроксимировать в пределах любого постоянного множителя, если только P = NP, показав, что подход Карпа к редукции обобщается до определенного типа редукции аппроксимируемости. [3] Однако следует отметить, что они могут отличаться от стандартных версий оптимизации проблем, которые могут иметь алгоритмы аппроксимации (как в случае максимального разреза).