В теории сложности вычислений , 21 NP-полные задачи Карпа представляют собой набор вычислительных задач , которые являются NP-полными . В своей статье 1972 года «Сводимость среди комбинаторных проблем» [1] Ричард Карп использовал теорему Стивена Кука 1971 года о том, что проблема логической выполнимости является NP-полной [2] (также называемая теоремой Кука-Левина ), чтобы показать, что существует за полиномиальное время сокращения многих один из булевой задачи выполнимости к каждому из 21 комбинаторных и графика теоретическоговычислительные задачи, тем самым показывая, что все они NP-полны. Это было одной из первых демонстраций того, что многие естественные вычислительные проблемы, возникающие в информатике , трудноразрешимы , и вызвало интерес к изучению NP-полноты и проблемы P в сравнении с NP .
Проблемы
Ниже показана 21 задача Карпа, многие из которых имеют свои оригинальные названия. Вложенность указывает направление используемых сокращений. Например, было показано , что Knapsack является NP-полным за счет уменьшения Exact cover до Knapsack .
- Выполнимость : проблема логической выполнимости для формул в конъюнктивной нормальной форме (часто называемая SAT)
- 0–1 целочисленное программирование (вариант, в котором должны выполняться только ограничения, без оптимизации)
- Клика (см. Также задачу о независимом множестве )
- Комплект упаковки
- Крышка Vertex
- Установить покрытие
- Набор узлов обратной связи
- Дуга обратной связи установлена
- Схема направленного Гамильтона (имя Карпа, теперь обычно называемое направленным гамильтоновым циклом )
- Ненаправленный гамильтонов цикл (имя Карпа, теперь обычно называемый неориентированным гамильтоновым циклом )
- Удовлетворение не более чем с 3 литералами на предложение (эквивалент 3-SAT)
- Хроматическое число (также называемое проблемой раскраски графа )
- Обложка клики
- Точное покрытие
- Набор ударов
- Дерево Штейнера
- 3-х мерное соответствие
- Ранец (определение Ранца, данное Карпом, ближе к сумме подмножества )
- Хроматическое число (также называемое проблемой раскраски графа )
Со временем было обнаружено, что многие проблемы могут быть решены эффективно, если ограничены особыми случаями, или могут быть решены в пределах любого фиксированного процента от оптимального результата. Тем не менее, Дэвид Цукерман показал в 1996 году, что каждая из этих 21 проблемы имеет версию с ограниченной оптимизацией, которую невозможно аппроксимировать в пределах любого постоянного множителя, если только P = NP, показав, что подход Карпа к редукции обобщается на конкретный тип уменьшения аппроксимируемости. [3] Однако обратите внимание, что они могут отличаться от стандартных оптимизационных версий задач, которые могут иметь алгоритмы аппроксимации (как в случае максимального отсечения).
Смотрите также
Заметки
- Перейти ↑ Karp 1972 .
- ^ Кук 1971 .
- Перейти ↑ Zuckerman 1996 .
Рекомендации
- Стивен Кук (1971). «Сложность процедур доказательства теорем» . Proc. 3-й ежегодный симпозиум ACM по теории вычислений (STOC) . С. 151–158. DOI : 10,1145 / 800157.805047 . S2CID 7573663 .
- Ричард М. Карп (1972). «Сводимость среди комбинаторных проблем» (PDF) . В RE Miller; Дж. У. Тэтчер; JD Bohlinger (ред.). Сложность компьютерных вычислений . Нью-Йорк: Пленум. С. 85–103. DOI : 10.1007 / 978-1-4684-2001-2_9 . ISBN 978-1-4684-2003-6.
- Цукерман, Дэвид (1996). «О неприпримых версиях NP-полных задач» . SIAM Journal on Computing . 25 (6): 1293–1304. DOI : 10,1137 / S0097539794266407 . [1]