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

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

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

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

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

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

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