Эта странная математика

Разумно предположить, что множество NP больше, чем P, ведь оно включает и те задачи, которые можно решить только на машине Тьюринга, обладающей сверхспособностями – поразительной везучестью или фантастической производительностью. Но на сегодня никем пока не доказано, что обычная ДМТ не способна на все то же, что по силам НМТ, хотя такое предположение и кажется весьма правдоподобным. Однако для математиков есть огромная разница между разумным предположением и достоверностью. Пока нет убедительных свидетельств иного, всегда остается возможность, что кто-то докажет равенство множеств N и NP – почему, собственно, проблема и носит такое название. Миллион долларов – сумма немалая, но как ее получить, если для этого нужно доказать (или опровергнуть), что

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

. В этом случае утверждение “P = NP” будет истинным.

Первая NP-полная задача, названная задачей выполнимости булевых формул, или SAT[21], была сформулирована в 1971 году американско-канадским математиком и специалистом в области теории вычислительных систем Стивеном Куком. Ее можно выразить в терминах логических вентилей. Имеется схема, состоящая из произвольного множества логических вентилей и входов (но не имеющая обратной связи) и ровно одного выхода. Вопрос: можно ли найти такое сочетание входов, при котором выход “включится”? В принципе, решение всегда можно искать перебором всех возможных сочетаний входов в системе, но это все равно что использовать экспоненциальный алгоритм. Чтобы доказать равенство

P и NP, придется доказать, что есть более быстрый – полиномиальный – способ получить ответ.

SAT – хотя и первая, но не самая известная из NP-полных задач. Эта честь принадлежит задаче коммивояжера, уходящей корнями в середину XIX века. В руководстве для коммивояжеров, опубликованном в 1832 году, шла речь о наиболее эффективном способе объехать ряд городов в Германии и Швейцарии. Научную формулировку задаче впервые дали пару десятилетий спустя ирландский физик и математик Уильям Гамильтон и англиканский священник и математик Томас Киркман. Предположим, что коммивояжеру нужно объехать множество городов и ему известно расстояние (не обязательно по прямому маршруту) между каждой парой городов. Необходимо найти кратчайший маршрут, по которому можно объехать все города и вернуться в исходный. Только в 1972 году было доказано, что эта задача является NP-полной (то есть что построение полиномиального алгоритма для ее решения докажет равенство P

и NP). Это объясняет, почему не одно поколение математиков, в последнее время даже вооруженных компьютерами, сталкивалось с трудностями при поиске оптимальных решений для сложных маршрутов.

Понять условия задачи коммивояжера не составит труда никому, а вот решить ее ничуть не проще, чем любую другую NP-полную задачу – все они чрезвычайно сложны. Математикам не дает покоя то, что построение полиномиального алгоритма для любой NP-полной задачи докажет, что P = NP. Последствия этого будут очень серьезны: в частности, это будет означать, что существует полиномиальный алгоритм для взлома RSA – метода криптографической защиты (мы еще поговорим о нем позже), на который мы полагаемся ежедневно, например, при получении банковских услуг. Хотя, скорее всего, такого алгоритма все же не существует.