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