21 NP-полная задача Карпа - Karp's 21 NP-complete problems

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

Проблемы

Ниже показана 21 задача Карпа, многие из которых имеют свои оригинальные названия. Вложенность указывает направление используемых сокращений. Например, было показано , что Knapsack является NP-полным за счет уменьшения Exact cover до Knapsack .

• Выполнимость : проблема логической выполнимости для формул в конъюнктивной нормальной форме (часто называемая SAT)
  • 0–1 целочисленное программирование (вариант, в котором должны выполняться только ограничения, без оптимизации)
  • Клика (см. Также задачу о независимом множестве )
    • Комплект упаковки
    • Крышка Vertex
      • Установить покрытие
      • Набор узлов обратной связи
      • Дуга обратной связи установлена
      • Направленная цепь Гамильтона (имя Карпа, теперь обычно называемое направленным гамильтоновым циклом )
        • Ненаправленный гамильтонов цикл (имя Карпа, теперь обычно называемый неориентированным гамильтоновым циклом )
  • Удовлетворение не более чем с 3 литералами на предложение (эквивалент 3-SAT)
    • Хроматическое число (также называемое проблемой раскраски графа )
      • Обложка клики
      • Точное покрытие
        • Набор ударов
        • Дерево Штейнера
        • 3-х мерное соответствие
        • Ранец (определение Ранца, данное Карпом, ближе к сумме подмножества )
          • Последовательность заданий
          • Раздел
            • Максимальный разрез

Со временем было обнаружено, что многие проблемы могут быть решены эффективно, если ограничены особыми случаями, или могут быть решены в пределах любого фиксированного процента от оптимального результата. Тем не менее, Дэвид Цукерман показал в 1996 году, что каждая из этих 21 проблемы имеет версию с ограниченной оптимизацией, которую невозможно аппроксимировать в пределах любого постоянного множителя, если только P = NP, показывая, что подход Карпа к редукции обобщается на конкретный тип уменьшения аппроксимируемости. Однако обратите внимание, что они могут отличаться от стандартных оптимизационных версий задач, которые могут иметь алгоритмы аппроксимации (как в случае максимального сокращения).

Смотрите также

• Список NP-полных задач

Заметки

Рекомендации

• Стивен Кук (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]