NP-полная задача: определение и примеры¶

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

Формальное определение опирается на понятие полиномиальной сводимости. Задача L называется NP-полной, если она принадлежит классу NP и каждая задача из NP полиномиально сводится к L. Существование первой такой задачи доказал Стивен Кук в 1971 году, продемонстрировав NP-полноту задачи выполнимости булевых формул (SAT). Впоследствии Ричард Карп в 1972 году представил список из 21 NP-полной задачи, что положило начало систематическому изучению этого класса.

¶Классы P и NP

Для понимания NP-полноты необходимо различать классы P и NP. Класс P включает задачи, которые можно решить за полиномиальное время (например, сортировка массива). Класс NP состоит из задач, для которых можно проверить предложенное решение за полиномиальное время. Очевидно, что P ⊆ NP, однако вопрос о том, совпадают ли эти классы, остаётся открытым (проблема P vs NP). NP-полные задачи являются «кандидатами» на то, чтобы не принадлежать классу P, поскольку если хотя бы одна из них решается за полиномиальное время, то P = NP.

¶Свойства и значение

Ключевое свойство NP-полных задач — взаимная сводимость. Если задача A полиномиально сводится к задаче B, и A является NP-полной, то B также NP-полна (при условии, что B ∈ NP). Это позволяет выстраивать цепочки сведения и доказывать NP-полноту новых задач, не повторяя трудоёмкое доказательство Кука.

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

¶Классические примеры

¶Задача выполнимости булевых формул (SAT)

Дана булева формула в конъюнктивной нормальной форме. Требуется определить, существует ли набор значений переменных, при котором формула истинна. Это первая доказанная NP-полная задача. Её частный случай — задача 3-SAT, где каждая дизъюнкция содержит ровно три литерала, также NP-полна.

¶Задача о клике

Дан неориентированный граф и число k. Требуется определить, существует ли в графе полный подграф (клика) размера k. Задача NP-полна, хотя проверка того, что найденное множество вершин образует клику, выполняется за полиномиальное время.

¶Задача о вершинном покрытии

Дан граф и число k. Требуется выяснить, существует ли множество вершин размера не более k, такое что каждое ребро графа инцидентно хотя бы одной вершине из этого множества. Задача NP-полна и тесно связана с задачей о независимом множестве.

¶Задача коммивояжёра (TSP)

Дано n городов и матрица расстояний. Требуется найти кратчайший маршрут, посещающий каждый город ровно один раз и возвращающийся в исходный. В общей постановке (без ограничений на расстояния) задача NP-полна. Существуют частные случаи (например, евклидово расстояние), для которых известны полиномиальные приближённые алгоритмы.

¶Задача о сумме подмножества

Дано множество целых чисел и целевое число S. Требуется определить, существует ли подмножество, сумма элементов которого равна S. Задача NP-полна, хотя является псевдополиномиальной: её можно решить методом динамического программирования за время O(n·S).

¶Задача о рюкзаке

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

¶Задача о раскраске графа

Дан граф и число k. Требуется определить, можно ли раскрасить вершины в k цветов так, чтобы смежные вершины имели разные цвета. Для k ≥ 3 задача NP-полна; для k = 2 она решается за линейное время (проверка двудольности).

¶Задача о гамильтоновом цикле

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

¶Методы доказательства NP-полноты

Для доказательства NP-полноты новой задачи необходимо выполнить два шага:

1. Показать, что задача принадлежит классу NP (предъявить сертификат решения и алгоритм его проверки).
2. Построить полиномиальное сведение известной NP-полной задачи к данной.

На практике чаще всего используются сведения от 3-SAT, задачи о клике, вершинном покрытии или гамильтоновом цикле.

¶Практические аспекты

Несмотря на теоретическую неразрешимость за полиномиальное время, NP-полные задачи широко встречаются на практике: в логистике (маршрутизация транспорта), проектировании микросхем (размещение компонентов), биоинформатике (выравнивание последовательностей), расписаниях и планировании. Для них разработаны эффективные эвристические и приближённые алгоритмы, которые дают приемлемые решения за разумное время. Например, для задачи коммивояжёра существует алгоритм Кристофидеса с гарантированной точностью 3/2 от оптимума для метрического случая.

¶Открытые вопросы

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

¶Источники

• Гэри М., Джонсон Д. «Вычислительные машины и труднорешаемые задачи»
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ»
• Стивен Кук. «The Complexity of Theorem-Proving Procedures» (1971)
• Ричард Карп. «Reducibility Among Combinatorial Problems» (1972)