NP-твердость
В теории сложности вычислений вычислительная задача H называется NP-трудной если для каждой задачи L , которая может быть решена за недетерминированное полиномиальное время , существует сокращение за полиномиальное время от L до H. , что решение H занимает 1 единицу времени, решение H То есть, если предположить , можно использовать для решения L за полиномиальное время. [1] [2] Как следствие, поиск алгоритма с полиномиальным временем для решения одной NP-сложной задачи даст алгоритмы с полиномиальным временем для всех задач класса сложности NP . Поскольку предполагается, что P≠NP , маловероятно, что такой алгоритм существует. [3] Предполагается, что для решения NP-трудных задач не существует алгоритмов с полиномиальным временем, но это не доказано. [4] Простым примером NP-трудной задачи является задача о сумме подмножеств .
Неформально, если H NP-трудна, то решить ее по крайней мере так же сложно, как и задачи из NP . Однако обратное утверждение неверно: некоторые проблемы неразрешимы и, следовательно, их решить даже труднее, чем все проблемы из NP, но они, очевидно, не являются NP-сложными (если только P=NP). [5]
Определение [ править ]
H Проблема принятия решения является NP-сложной, когда для каждой проблемы L в NP существует полиномиальное сокращение числа «много-один» от L до H . [1] : 80
Другое определение состоит в том, чтобы потребовать, чтобы существовало полиномиальное сокращение NP-полной задачи G к H . [1] : 91 Поскольку любая проблема L в NP сводится за полиномиальное время к G , L, в свою очередь, сводится к H за полиномиальное время, поэтому из этого нового определения следует предыдущее. Он не ограничивает класс NP-трудных задачами решения, а также включает задачи поиска или задачи оптимизации .
Последствия [ править ]
Если P ≠ NP, то NP-сложные задачи невозможно решить за полиномиальное время.
Некоторые NP-сложные задачи оптимизации могут быть полиномиально аппроксимированы до некоторого постоянного коэффициента аппроксимации (в частности, в APX ) или даже до любого коэффициента аппроксимации (в PTAS или FPTAS ). Существует множество классов аппроксимации, каждый из которых позволяет аппроксимировать до определенного уровня. [6]
Примеры [ править ]
Все NP-полные задачи также являются NP-сложными (см. Список NP-полных задач ). Например, задача оптимизации поиска циклического маршрута с наименьшей стоимостью через все узлы взвешенного графа, широко известная как задача коммивояжера, является NP-трудной. [7] Еще одним примером является проблема суммы подмножества : для данного набора целых чисел, любое из их непустых подмножеств в сумме дает ноль? Это проблема принятия решения , и она оказывается NP-полной.
Существуют задачи принятия решения, которые являются NP-сложными , но не NP-полными, например проблема остановки . Это проблема, которая спрашивает: «Для данной программы и ее ввода будет ли она работать вечно?» Это вопрос «да / нет» , как и проблема принятия решения. Легко доказать, что проблема остановки NP-трудна, но не NP-полна. Например, проблему логической выполнимости можно свести к проблеме остановки, преобразовав ее в описание машины Тьюринга , которая пробует все присваивания значений истинности и когда находит такое, которое удовлетворяет формуле, она останавливается, а в противном случае переходит в бесконечный цикл. Также легко увидеть, что проблема остановки не относится к NP, поскольку все проблемы в NP разрешимы за конечное число операций, но проблема остановки, вообще говоря, неразрешима . Существуют также NP-сложные задачи, которые не являются ни NP-полными , ни неразрешимыми . Например, язык истинных количественных булевых формул разрешим в полиномиальном пространстве , но не в недетерминированном полиномиальном времени (если только NP = PSPACE ). [8]
Соглашение об именах NP [ править ]
NP-сложные задачи не обязательно должны быть элементами класса сложности NP. Поскольку NP играет центральную роль в вычислительной сложности , он используется в качестве основы нескольких классов:
- НАПРИМЕР
- Класс задач вычислительного решения, для которых любое заданное да -решение может быть проверено как решение за полиномиальное время с помощью детерминированной машины Тьюринга (или разрешимо с помощью недетерминированной машины Тьюринга за полиномиальное время).
- NP-жесткий
- Класс задач, которые по крайней мере так же сложны, как и самые сложные задачи в NP. Проблемы, которые являются NP-сложными, не обязательно должны быть элементами NP; более того, они могут быть даже неразрешимыми.
- NP-полный
- Класс задач решения, который содержит самые сложные задачи в NP. Каждая NP-полная задача должна находиться в NP.
- NP-легко
- Максимум так же сложно, как NP, но не обязательно в NP.
- NP-эквивалент
- Проблемы принятия решений, одновременно NP-сложные и NP-простые, но не обязательно NP.
- NP-средний
- Если P и NP различны, то в области NP существуют проблемы решения, которые находятся между P и NP-полными проблемами. (Если P и NP относятся к одному и тому же классу, то NP-промежуточных задач не существует, потому что в этом случае каждая NP-полная задача попадет в P, и по определению каждая проблема из NP может быть сведена к NP-полной задаче. )
Области применения [ править ]
NP-сложные проблемы часто решаются с помощью языков, основанных на правилах, в таких областях, как:
- Приблизительные вычисления
- Конфигурация
- Криптография
- Сбор данных
- Поддержка при принятии решения
- Филогенетика
- Планирование
- Мониторинг и контроль процессов
- Реестры или расписания
- Маршрутизация/маршрутизация транспортных средств
- Планирование
См. также [ править ]
Ссылки [ править ]
- ^ Перейти обратно: а б с Леувен, Ян ван , изд. (1998). Справочник по теоретической информатике . Том. А. Алгоритмы и сложность. Амстердам: Эльзевир. ISBN 0262720140 . OCLC 247934368 .
- ^ Кнут, Дональд (1974). «Постскриптум о NP-трудных задачах». Новости ACM SIGACT . 6 (2): 15–16. дои : 10.1145/1008304.1008305 . S2CID 46480926 .
- ^ Даниэль Пьер Бове; Пьерлуиджи Крещенци (1994). Введение в теорию сложности . Прентис Холл. п. 69. ИСБН 0-13-915380-2 .
- ^ «Shtetl-Optimized» Архив блога » Научное обоснование P≠NP» . www.scottaaronson.com . Проверено 25 сентября 2016 г.
- ^ «Является ли неразрешимое (дополнение R) подмножеством NP-трудного?» . Обмен стеками в области компьютерных наук . Проверено 9 февраля 2024 г.
- ^ Эскофье, Б.; Пашос, Б.Т. (2010). «Обзор структуры классов аппроксимации». Обзор компьютерных наук . 4 (1): 19–40.
- ^ Лоулер, Эл . ; Ленстра, JK ; Риннуй Кан, AHG; Шмойс, Д.Б. (1985), Проблема коммивояжера: экскурсия по комбинаторной оптимизации , John Wiley & Sons, ISBN 0-471-90413-9 .
- ^ Точнее, этот язык PSPACE-полный ; см., например, Вегенер, Инго (2005), Теория сложности: исследование пределов эффективных алгоритмов , Springer, стр. 189, ISBN 9783540210450 .
- Гэри, Майкл Р .; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . Серия книг по математическим наукам (1-е изд.). Нью-Йорк: WH Freeman and Company . ISBN 9780716710455 . МР 0519066 . OCLC 247570676 .