Карпс 21 NP-полные задачи - Karps 21 NP-complete problems

В теория сложности вычислений, 21 NP-полная задача Карпа представляют собой набор вычислительные проблемы которые НП-полный. В своей статье 1972 года "Сводимость комбинаторных задач" ^[1] Ричард Карп использовал Стивен Кук теорема 1971 года о том, что проблема логической выполнимости NP-полный^[2] (также называемый Теорема Кука-Левина ), чтобы показать, что существует полиномиальное время много-одно сокращение от задачи логической выполнимости к каждому из 21 комбинаторный и теоретический график вычислительные задачи, тем самым показывая, что все они NP-полны. Это была одна из первых демонстраций того, что многие естественные вычислительные проблемы, возникающие в Информатика находятся вычислительно трудноразрешимый, что вызвало интерес к изучению NP-полноты и Проблема P против NP.

Проблемы

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

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

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

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

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

Примечания

1. Карп 1972. Ошибка sfn: цель отсутствует: CITEREFKarp1972 (помощь)
2. Повар 1971. Ошибка sfn: нет цели: CITEREFCook1971 (помощь)
3. Цукерман 1996.

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

• Стивен Кук (1971). «Сложность процедур доказательства теорем». Proc. 3-й ежегодный симпозиум ACM по теории вычислений (STOC). С. 151–158. Дои:10.1145/800157.805047.
• Ричард М. Карп (1972). «Сводимость среди комбинаторных проблем» (PDF). У Р. Э. Миллера; Дж. У. Тэтчер; J.D. Bohlinger (ред.). Сложность компьютерных вычислений. Нью-Йорк: Пленум. С. 85–103. Дои:10.1007/978-1-4684-2001-2_9. ISBN  978-1-4684-2003-6.
• Цукерман, Дэвид (1996). «О неприблизимых версиях NP-полных задач». SIAM Журнал по вычислениям. 25 (6): 1293–1304. Дои:10.1137 / S0097539794266407. [1]