NP-трудность

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

Диаграмма Эйлера взаимоотношения между классами сложности P, NP, NP-complete (NP-полными задачами), NP-hard (NP-трудными задачами) в случае, если P≠NP и если P=NP

Формальное определение: задача разрешимости $\text{[math]}$ $\text{[math]}$ $H$ $H$ является NP-трудной, если любая задача $\text{[math]}$ $\text{[math]}$ $L$ $L$ из NP может быть сведена за полиномиальное время к $\text{[math]}$ $\text{[math]}$ $H$ $H$ . Эквивалентно условие требует, чтобы каждая задача $\text{[math]}$ $\text{[math]}$ $L$ $L$ в NP могла быть решена за полиномиальное время с оракулом для $\text{[math]}$ $\text{[math]}$ $H$ $H$ ^[1]^[2]. Как следствие, алгоритм с полиномиальным временем для решения любой NP-трудной задачи даст алгоритмы с полиномиальным временем для всех задач в NP.

Считается что алгоритмов с полиномиальным временем для NP-трудных задач не существует, но это не доказано (см. проблему P≠NP)^[3]. Более того, класс P, в котором все задачи решаются за полиномиальное время, содержится в классе NP^[4].

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

Наименования классов в NP-трудностиПравить

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

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

ПримерыПравить

Задача о сумме подмножеств: есть ли в заданном наборе целых чисел непустое их подмножество, дающее в сумме ноль? Это задача разрешимости, и она является NP-полной.

Задача коммивояжера — оптимизационная задача поиска циклического маршрута с наименьшей стоимостью через все узлы взвешенного графа. Это NP-трудная задача^[5].

Проблема останова — задача, являющаяся NP-трудной, но не NP-полной. Задача звучит: «Дана программа и её ввод, остановится ли программа?» Легко доказать, что проблема остановки NP-трудна, но не NP-полна — булева проблема выполнимости может быть сведена к проблеме останова путем преобразования её в описание машины Тьюринга, которая пробует все возможные входные данные, и когда она находит те, которые удовлетворяют формуле, она останавливается, а в противном случае входит в бесконечный цикл. Также проблема останова не содержится в NP, так как все проблемы в NP разрешимы за конечное число операций, а проблема останова неразрешима.

Существуют NP-трудные задачи, которые не являются ни NP-полными, ни неразрешимыми . Например, язык истинных квантифицированных булевых формул^[en] разрешим в полиномиальном пространстве, но не в недетерминированном полиномиальном времени (если верно NP ≠ PSPACE)^[6].

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

С NP-трудными проблемами сталкиваются чаще всего в таких сферах, как:

ПримечанияПравить

↑ Handbook of Theoretical Computer Science. — Amsterdam : Elsevier, 1998. — Vol. A, Algorithms and complexity. — ISBN 0262720140.
↑ Knuth, Donald (1974). “Postscript about NP-hard problems”. ACM SIGACT News. 6 (2): 15—16. DOI:10.1145/1008304.1008305.
↑ Shtetl-Optimized » Blog Archive » The Scientific Case for P≠NP (неопр.). www.scottaaronson.com. Дата обращения: 25 сентября 2016.
↑ PHYS771 Lecture 6: P, NP, and Friends (неопр.). www.scottaaronson.com. Дата обращения: 25 сентября 2016.
↑ Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H. G. & Shmoys, D. B. (1985), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, John Wiley & Sons, ISBN 0-471-90413-9, <https://archive.org/details/travelingsalesma00lawl> .
↑ Точнее, этот язык PSPACE-полон^[en]; см. Wegener, Ingo (2005), Complexity Theory: Exploring the Limits of Efficient Algorithms, Springer, с. 189, ISBN 9783540210450, <https://books.google.com/books?id=1fo7_KoFUPsC&pg=PA189> .

[Leeuwen-1] Handbook of Theoretical Computer Science. — Amsterdam : Elsevier, 1998. — Vol. A, Algorithms and complexity. — ISBN 0262720140.

[2] Knuth, Donald (1974). “Postscript about NP-hard problems”. ACM SIGACT News. 6 (2): 15—16. DOI:10.1145/1008304.1008305.

[3] Shtetl-Optimized » Blog Archive » The Scientific Case for P≠NP (неопр.). www.scottaaronson.com. Дата обращения: 25 сентября 2016.

[4] PHYS771 Lecture 6: P, NP, and Friends (неопр.). www.scottaaronson.com. Дата обращения: 25 сентября 2016.

[5] Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H. G. & Shmoys, D. B. (1985), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, John Wiley & Sons, ISBN 0-471-90413-9, <https://archive.org/details/travelingsalesma00lawl> .

[6] Точнее, этот язык PSPACE-полон^[en]; см. Wegener, Ingo (2005), Complexity Theory: Exploring the Limits of Efficient Algorithms, Springer, с. 189, ISBN 9783540210450, <https://books.google.com/books?id=1fo7_KoFUPsC&pg=PA189> .

[1]

[2]

[3]

[4]

[5]

[6]