Из Википедии, бесплатной энциклопедии
  (Перенаправлен с NP-hard )
Перейти к навигации Перейти к поиску
Для более мягкого введения см. Проблема 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-трудностей проблемами решения, а также включает проблемы поиска или проблемы оптимизации .

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

Если 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 . |volume= has extra text (help)
  2. ^ Кнут, Дональд (1974). «Постскриптум о NP-сложных задачах». Новости ACM SIGACT . 6 (2): 15–16. DOI : 10.1145 / 1008304.1008305 . S2CID 46480926 . 
  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-полным ; см., например, Wegener, Ingo (2005), « Теория сложности: изучение пределов эффективных алгоритмов» , Springer, стр. 189, ISBN 9783540210450.
  • Майкл Р. Гарей и Дэвид С. Джонсон (1979). Компьютеры и непоколебимость: руководство по теории NP-полноты . WH Freeman. ISBN 0-7167-1045-5.