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

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

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

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

Определение [ править ]

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

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

Последствия [ править ]

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

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

Примеры [ править ]

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

Существуют NP-трудные, но не NP-полные проблемы решения, такие как проблема остановки . Это проблема, которая спрашивает: "Будет ли она работать вечно при наличии программы и ее входных данных?" Это вопрос « да / нет», и это проблема решения. Легко доказать, что проблема остановки является NP-сложной, но не 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. ^ a b c Леувен, Ян ван , изд. (1998). Справочник по теоретической информатике . Vol. A, Алгоритмы и сложность. Амстердам: Эльзевир. ISBN 0262720140. OCLC  247934368 .
  2. ^ Кнут, Дональд (1974). «Постскриптум о NP-сложных задачах». Новости ACM SIGACT . 6 (2): 15–16. DOI : 10.1145 / 1008304.1008305 .
  3. ^ Даниэль Пьер Бове; Пьерлуиджи Крещенци (1994). Введение в теорию сложности . Прентис Холл. п. 69. ISBN 0-13-915380-2.
  4. ^ «П и НП» . www.cs.uky.edu . Архивировано из оригинала на 2016-09-19 . Проверено 25 сентября 2016 .
  5. ^ «Shtetl-Optimized» Архив блога »Научное обоснование P ≠ NP» . www.scottaaronson.com . Проверено 25 сентября 2016 .
  6. ^ «PHYS771 Лекция 6: P, NP и друзья» . www.scottaaronson.com . Проверено 25 сентября 2016 .
  7. ^ VJ Rayward-Smith (1986). Первый курс вычислимости . Блэквелл. п. 159. ISBN. 0-632-01307-9.
  8. ^ Лоулер, EL ; Lenstra, JK ; Ринну Кан, AHG; Шмойс, ДБ (1985), Проблема коммивояжера: экскурсия по комбинаторной оптимизации , John Wiley & Sons, ISBN 0-471-90413-9.
  9. ^ Точнее, этот язык является PSPACE-полным ; см., например, Вегенер, Инго (2005), Теория сложности: изучение пределов эффективных алгоритмов , Springer, стр. 189, ISBN 9783540210450.
  • Майкл Р. Гэри и Дэвид С. Джонсон (1979). Компьютеры и непреодолимость: руководство по теории NP-полноты . WH Freeman. ISBN 0-7167-1045-5.