NP-твердость - NP-hardness

Для более мягкого введения см. P против проблемы NP.
Диаграмма Эйлера для P, NP, NP-полного и NP-трудного множества задач.
Диаграмма Эйлера за п, НП, NP-полный и NP-жесткий набор задач. Левая часть справедлива в предположении, что P ≠ NP, в то время как правая часть действительна в предположении, что P = NP (за исключением того, что пустой язык и его дополнение никогда не являются NP-полными)

В теория сложности вычислений, NP-твердость (недетерминированное полиномиальное время твердость) является определяющим свойством класса задач, которые неформально «по крайней мере так же сложны, как самые сложные задачи в НП ". Простым примером NP-трудной задачи является проблема суммы подмножества.

Более точная спецификация: проблема ЧАС NP-сложно, когда каждая проблема L в НП может быть уменьшенный в полиномиальное время к ЧАС; то есть, предполагая решение для ЧАС занимает 1 единицу времени, ЧАСРешение может быть использовано для решения L за полиномиальное время.[1][2] Как следствие, поиск алгоритма с полиномиальным временем для решения любой NP-трудной задачи даст алгоритмы с полиномиальным временем для всех проблем в NP. Как есть подозрение, что п НП, маловероятно, что такой алгоритм существует.[3]

Распространенное заблуждение состоит в том, что НП в "NP-hard" означает "неполиномиальный", тогда как на самом деле это означает "недетерминированный полиномиально допустимые задачи ".[4] Есть подозрение, что не существует алгоритмов с полиномиальным временем для NP-сложных задач, но это не было доказано.[5] Более того, класс п, в котором все задачи могут быть решены за полиномиальное время, содержится в НП учебный класс.[6]

Определение

А проблема решения ЧАС NP-сложно, когда для каждой проблемы L в НП имеется редукция "много-один" за полиномиальное время из L к ЧАС.[1]:80Эквивалентное определение требует, чтобы каждая проблема L в НП можно решить в полиномиальное время по машина оракула с оракулом для ЧАС.[7] Неформально можно представить алгоритм, который вызывает такую ​​машину-оракул как подпрограмму для решения ЧАС и решает L за полиномиальное время, если для вычисления вызова подпрограммы требуется только один шаг.

Другое определение состоит в том, чтобы требовать полиномиального сокращения от НП-полный проблема грамм к ЧАС.[1]:91 Как любая проблема L в NP сводится за полиномиальное время к грамм, L сводится в свою очередь к ЧАС за полиномиальное время, поэтому из этого нового определения следует предыдущее. Как ни странно, он не ограничивает класс NP-трудных задач решениями, а также включает проблемы с поиском или же проблемы оптимизации.

Последствия

Если P ≠ NP, то NP-сложные задачи не могут быть решены за полиномиальное время.

Некоторые NP-сложные задачи оптимизации могут быть полиномиальными. приблизительный с точностью до некоторого постоянного отношения аппроксимации (в частности, в APX ) или даже до любого отношения аппроксимации (в PTAS или же FPTAS ).

Примеры

Примером NP-сложной задачи является решение проблема суммы подмножества: учитывая набор целых чисел, суммируется ли какое-либо непустое их подмножество до нуля? Это проблема решения и оказывается NP-полным. Другой пример NP-трудной задачи - это задача оптимизации поиска циклического маршрута с наименьшей стоимостью через все узлы взвешенного графа. Это широко известно как задача коммивояжера.[8]

Есть проблемы с решением, которые NP-жесткий но нет НП-полный такой как проблема остановки. Это проблема, которая спрашивает: "Будет ли она работать вечно при наличии программы и ее входных данных?" Это да/нет вопрос и это проблема решения. Легко доказать, что проблема остановки является NP-сложной, но не NP-полной. Например, Проблема логической выполнимости можно свести к проблеме остановки, преобразовав ее к описанию Машина Тьюринга это пробует все значение истины присваивания, и когда он находит тот, который удовлетворяет формуле, он останавливается, а в противном случае он переходит в бесконечный цикл. Также легко увидеть, что проблема остановки не в НП поскольку все проблемы в NP разрешимы за конечное число операций, но проблема остановки, в общем, неразрешимый. Есть также NP-сложные проблемы, которые ни НП-полный ни Неразрешимый. Например, язык истинные количественные булевы формулы разрешима в полиномиальное пространство, но не за недетерминированное полиномиальное время (если NP = PSPACE ).[9]

Соглашение об именах NP

NP-сложные задачи не обязательно должны быть элементами класса сложности NP, поскольку NP играет центральную роль в вычислительная сложность, он лежит в основе нескольких классов:

НП
Класс вычислительных задач решения, для которых задана да-решение может быть проверено как решение за полиномиальное время с помощью детерминированной машины Тьюринга (или разрешимый по недетерминированный Машина Тьюринга за полиномиальное время).
NP-жесткий
Класс задач, которые не менее сложны, чем самые сложные задачи в NP. Проблемы, которые являются NP-сложными, не обязательно должны быть элементами NP; более того, они могут быть даже неразрешимыми.
НП-полный
Класс задач решения, который содержит самые сложные проблемы в NP. Каждая NP-полная задача должна быть в NP.
NP-easy
Самое большее, чем NP, но не обязательно в NP.
NP-эквивалент
Решение задач, которые одновременно NP-трудны и NP-легки, но не обязательно в NP.
НП-средний
Если P и NP различны, то существуют проблемы решения в области NP, которые попадают между P и NP-полными проблемами. (Если P и NP являются одним и тем же классом, то NP-промежуточные проблемы не существуют, потому что в этом случае каждая NP-полная проблема попала бы в P, и по определению каждая проблема в NP может быть сведена к NP-полной проблеме. )

Области применения

NP-сложные проблемы часто решаются с помощью языков, основанных на правилах, в таких областях, как:

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

  1. ^ а б c Леувен, Ян ван, изд. (1998). Справочник по теоретической информатике. Vol. A, Алгоритмы и сложность. Амстердам: Эльзевир. ISBN  0262720140. OCLC  247934368.
  2. ^ Кнут, Дональд (1974). «Постскриптум о NP-сложных задачах». Новости ACM SIGACT. 6 (2): 15–16. Дои:10.1145/1008304.1008305.
  3. ^ Даниэль Пьер Бове; Пьерлуиджи Крещенци (1994). Введение в теорию сложности. Прентис Холл. п. 69. ISBN  0-13-915380-2.
  4. ^ «П и НП». www.cs.uky.edu. Архивировано из оригинал в 2016-09-19. Получено 2016-09-25.
  5. ^ «Shtetl-Optimized» Архив блога »Научное обоснование P ≠ NP». www.scottaaronson.com. Получено 2016-09-25.
  6. ^ "PHYS771 Лекция 6: P, NP и друзья". www.scottaaronson.com. Получено 2016-09-25.
  7. ^ В. Дж. Рэйвард-Смит (1986). Первый курс вычислимости. Блэквелл. п. 159. ISBN  0-632-01307-9.
  8. ^ Лоулер, Э.; Ленстра, Дж. К.; Rinnooy Kan, A.H.G .; Шмойс, Д. Б. (1985), Задача коммивояжера: обзор комбинаторной оптимизации, Джон Уайли и сыновья, ISBN  0-471-90413-9.
  9. ^ Точнее, этот язык PSPACE-полный; см., например, Вегенер, Инго (2005), Теория сложности: изучение границ эффективных алгоритмов, Springer, стр. 189, ISBN  9783540210450.