21 NP-полная задача Карпа

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

Проблемы

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

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

Приближения

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

См. также

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

Ссылки

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