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