Книга: Золотой билет

P против NP

P против NP

Некоторые задачи заставили институтских исследователей изрядно попотеть. Давайте их перечислим: поиск клики, поиск гамильтонова пути (вторая игра со скипетром), раскраска карт и построение максимального разреза. У всех этих задач есть одна общая черта: для них легко проверить, является ли найденное решение верным. Зная всех членов общества «Альфа», можно без особых затруднений убедиться в том, что все они дружат между собой, а следовательно – образуют клику. Предполагаемое решение игры «Передай скипетр – 2» можно легко протестировать, просто начав в нее играть. Когда все дома раскрашены, можно за вполне разумное время проверить, что цвета любых двух соседних домов различаются. И, наконец, когда ученики уже разбиты на две группы, директор школы легко подсчитает число разорванных вражеских связей.

В теории сложности вычислений класс задач, для которых можно быстро проверить предполагаемое решение, обозначается NP (где N значит «недетерминированная машина Тьюринга», а P – «полиномиальное время», если уж вам так интересно). Наиболее известные представители класса NP – это как раз поиск клики, поиск гамильтонова пути, раскраска карт и построение максимального разреза.

Обратите внимание, что в классе P, в отличие от класса NP, решение можно быстро найти. Примеры – кратчайший путь, максимальное число паросочетаний, эйлеров путь (первая игра со скипетром) и минимальный разрез.

А что, если быстрый алгоритм поиска клики существует? Если в один прекрасный день какой-нибудь гениальный аспирант разработает простой метод нахождения гамильтонова пути, эффективный алгоритм раскраски карт или быстрый способ построения максимального разреза? Вдруг все эти проблемы на самом деле лежат в классе P – так же как и задачи о кратчайшем пути, максимальном числе паросочетаний, эйлеровом пути и минимальном разрезе? Такое вполне возможно; может даже оказаться, что быстрый алгоритм существует для всех задач из NP. Но пока мы этого не знаем.

В этом и заключается суть проблемы равенства (или неравенства) классов P и NP. Если P = NP, мы попадаем в совершенный мир, где для любой задачи из NP существуют эффективные алгоритмы, и можно не только быстро проверить предполагаемое решение, но и быстро найти самый оптимальный вариант. И наоборот – если найдется хоть одна задача из NP, для которой эффективного алгоритма не существует, это будет означать, что P ? NP.

Вопрос о равенстве P и NP – одна из центральных проблем вычислительной техники, а возможно, и всей математики. Многочисленные попытки ученых доказать равенство классов и разработать быстрые алгоритмы для поиска клики или гамильтонова пути, а также других NP-задач, успехом не увенчались. С неравенством классов дело обстоит еще сложнее: ведь для обоснования того факта, что P ? NP, нужно доказать невозможность построения быстрого алгоритма для клики или других задач из NP. Но как вы докажете невозможность чего бы то ни было? До сих пор ни в том, ни в другом направлении не было получено сколько-нибудь значимых результатов. Проблема P и NP настолько важна, что Математический институт Клэя предложил миллион долларов за ее решение. А я загорелся идеей написать эту книгу.

Оглавление книги