NP-полнота

NP-полнота — это свойство некоторых задач из класса NP (недетерминированно полиномиальных) быть самыми сложными в этом классе. Задача является NP-полной, если она принадлежит классу NP и к ней можно свести любую другую задачу из NP за полиномиальное время. Другими словами, NP-полные задачи являются «эталонными» для класса NP: если для какой-либо из них удастся найти эффективный (полиномиальный) алгоритм решения, то все задачи класса NP будут решаемы за полиномиальное время. И наоборот, если для хотя бы одной NP-полной задачи доказана невозможность полиномиального решения, то ни одна NP-полная задача не может быть решена за полиномиальное время.

История

Понятие NP-полноты было введено в начале 1970-х годов как результат исследований по теории сложности вычислений. Основополагающие работы принадлежат независимо работавшим Стивену Куку (Канада, затем США) и Леониду Левину (СССР).

1971 год: Стивен Кук опубликовал статью «Сложность процедур вывода теорем», в которой впервые сформулировал понятие NP-полноты и доказал NP-полноту задачи выполнимости булевых формул (SAT). Это доказательство стало фундаментом для всей теории.
1973 год: Леонид Левин (в СССР) опубликовал работу «Универсальные задачи перебора», в которой независимо от Кука доказал NP-полноту задачи SAT (называемой им «задачей выполнимости») и ещё нескольких задач.
1972 год: Ричард Карп (США) расширил работу Кука, опубликовав список из 21 NP-полной задачи, включая такие классические, как задача о вершинном покрытии, о клике, о гамильтоновом цикле и задача коммивояжёра. Эта работа доказала широкую применимость концепции.

Открытие NP-полноты имело огромное значение: оно позволило не доказывать для каждой сложной переборной задачи её принципиальную трудность по отдельности, а свести её к уже известной NP-полной задаче. Это дало практическое объяснение тому, почему многие важные оптимизационные и переборные задачи (в расписании, логистике, криптографии, биоинформатике) оказались исключительно сложны для точного решения за приемлемое время.

Определения и формальная основа

Класс NP

NP (Nondeterministic Polynomial time) — это класс задач, для которых существует алгоритм, проверяющий правильность предложенного решения за полиномиальное время. При этом сам процесс поиска решения может занимать экспоненциальное время. Классический пример — задача о коммивояжёре: проверить, что данный маршрут короче заданной длины, можно быстро, но найти оптимальный маршрут среди всех возможных — очень трудно.

Понятие сводимости

Центральное понятие для определения NP-полноты — полиномиальная сводимость (сводимость по Карпу). Задача A сводится к задаче B за полиномиальное время, если существует алгоритм, который за полиномиальное время преобразует любой вход задачи A во вход задачи B таким образом, что ответ для задачи A («да»/«нет») совпадает с ответом для задачи B на преобразованном входе. Если это так, то говорят, что A ≤P B (A полиномиально сводится к B).

Если A ≤P B, и задача B решается за полиномиальное время, то и задача A решается за полиномиальное время. Соответственно, если A ≤P B, и задача A является «трудной», то и задача B не может быть «лёгкой» — она не менее трудна, чем A.

Определение NP-полноты

Формально задача Q называется NP-полной, если выполняются два условия:

Принадлежность к NP: Q ∈ NP (существует полиномиальный алгоритм верификации).
NP-трудность: Для любой задачи R ∈ NP существует полиномиальная сводимость R ≤P Q (любая задача из NP сводится к Q).

Из второго условия следует, что NP-полные задачи являются самыми сложными в классе NP: если для какой-либо из них найден полиномиальный алгоритм, то и для всех задач из NP он найдётся (P = NP).

NP-трудная задача — это задача, которая удовлетворяет только второму условию, но не обязательно первому. Иными словами, любая задача из NP сводится к NP-трудной, но сама NP-трудная задача может не принадлежать классу NP (например, оптимальная задача коммивояжёра, где требуется не ответ «да/нет», а найти маршрут минимальной длины — она NP-трудная, но не NP-полная).

Известные NP-полные задачи

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

Классические задачи

Задача выполнимости булевых формул (SAT): Дана булева формула в конъюнктивной нормальной форме (КНФ). Существует ли набор значений переменных, при котором формула истинна? (Первая доказанная NP-полная задача).
Задача коммивояжёра (TSP) — распознавательная версия: Существует ли маршрут, проходящий через все заданные города ровно по одному разу и возвращающийся в начальный город, длина которого не превышает заданного числа L?
Задача о вершинном покрытии: Существует ли множество вершин графа размером не более K, такое что каждое ребро графа инцидентно хотя бы одной вершине из этого множества?
Задача о клике: Существует ли в неориентированном графе полный подграф (клика) размера не менее K?
Задача о сумме подмножества: Дано множество целых чисел и число S. Существует ли непустое подмножество, сумма элементов которого равна S?
Задача о раскраске графа (распознавательная версия): Можно ли вершины графа покрасить в K цветов так, чтобы смежные вершины имели разный цвет?

Прикладные NP-полные задачи

Задача о рюкзаке: Дано множество предметов с весом и стоимостью, а также вместимость рюкзака. Найти подмножество предметов максимальной суммарной стоимости, общий вес которого не превышает вместимость. (Одна из самых изученных NP-полных задач; на её основе строится криптосистема Меркла — Хеллмана, которая, однако, была взломана).
Задача о расписании: Требуется составить оптимальное расписание выполнения работ на нескольких машинах при заданных ограничениях (время выполнения, зависимости). Многие варианты являются NP-полными.
Задача о наибольшей общей подпоследовательности (LCS) — общая версия для нескольких строк.
Задача о поиске точного совпадения шаблона — в некоторых вариациях.

Классы P, NP, NP-полные и NP-трудные

Взаимосвязь этих классов схематично изображается на диаграмме Венна. Однако до сих пор не доказано строго, что P ≠ NP или P = NP. Это одна из семи «задач тысячелетия» (Millennium Problems) — самых сложных и важных нерешённых математических проблем. Математический институт Клэя назначил за её решение приз в 1 миллион долларов США.

P — множество задач, решаемых за полиномиальное время (например, проверка простоты числа, поиск кратчайшего пути в графе).
NP — множество задач, чьё решение можно проверить за полиномиальное время. Очевидно, что P ⊆ NP (если задача решается быстро, то и проверить решение быстро).
NP-полные — подмножество NP, «самые сложные» задачи.
NP-трудные — задачи, к которым сводятся все задачи из NP, но которые сами могут не входить в NP (например, оптимизационные версии).

Если P = NP, то все NP-полные задачи решаемы за полиномиальное время. Если P ≠ NP, то ни одна NP-полная задача не может быть решена за полиномиальное время. Большинство специалистов по теории сложности склоняются к гипотезе P ≠ NP, то есть к тому, что точное решение NP-полных задач в общем случае требует экспоненциального времени.

Практическое значение

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

Приближённые алгоритмы: Для многих NP-полных задач существуют алгоритмы, которые гарантированно находят решение, незначительно (в худшем случае) отличающееся от оптимального. Например, для задачи коммивояжёра существует алгоритм, находящий маршрут не более чем в 1,5 раза длиннее оптимального.
Эвристические алгоритмы: Вместо гарантированной точности применяются эвристики, которые на практике часто находят (почти) оптимальные решения для большинства входных данных. Примеры: генетические алгоритмы, имитация отжига, муравьиные алгоритмы.
Экспоненциальные алгоритмы для малых размеров: Для задачи с небольшим числом элементов (например, до 30-50) можно использовать точные алгоритмы, работающие за экспоненциальное время, которые на практике всё равно будут приемлемы.
Параметризованная сложность: Для некоторых NP-полных задач существуют точные алгоритмы, время работы которых экспоненциально зависит от некоторого малого параметра, а не от общего размера входных данных.

Понимание NP-полноты является фундаментальным для современной компьютерной науки. Оно позволяет разработчикам алгоритмов сразу понять, что искать точный полиномиальный алгоритм для данной задачи бессмысленно, и сосредоточиться на приближённых или эвристических подходах. Поэтому многие оптимизационные системы в промышленности (логистика, производство, биоинформатика, проектирование электронных схем) основаны на эвристиках и приближённых методах.

Критика и ограничения

Хотя концепция NP-полноты является мощным инструментом, она имеет ограничения:

Анализ худшего случая: Теория NP-полноты рассматривает сложность в худшем случае. На практике многие трудные задачи часто оказываются лёгкими для большинства типичных входных данных.
Выбор сводимости: Используется полиномиальная сводимость по Карпу. Существуют и другие, более сильные виды сводимости, которые могут менять картину, особенно для детерминированных алгоритмов.
Односторонность: Доказательство NP-полноты не даёт конструктивного способа решить задачу — оно лишь говорит, что если полиномиальный алгоритм существует, то он будет решением всех задач NP, включая SAT, что маловероятно.
Неопределённость P vs NP: До тех пор, пока не доказано, что P ≠ NP, нельзя гарантировать, что никакая NP-полная задача не является полиномиальной. Поэтому любое утверждение о том, что «эту задачу невозможно решить эффективно», носит гипотетический характер, хотя и чрезвычайно правдоподобный с точки зрения практики.

Источники

Кук С. «Сложность процедур вывода теорем», 1971.
Карп Р. «Редуцируемость комбинаторных задач», 1972.
Левин Л. «Универсальные задачи перебора», 1973.
Гэри М., Джонсон Д. «Вычислительные машины и труднорешаемые задачи», 1982.
Ахо А., Хопкрофт Д., Ульман Дж. «Структуры данных и алгоритмы», 2000.

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →