Эта странная математика. На краю бесконечности и за ним - [32]

В принципе, при наличии достаточного времени ДМТ под силу любая задача, с которой может справиться НМТ. Загвоздка как раз в “достаточности” времени. Ту же самую задачу, которую ДМТ выполняет за экспоненциальное время, НМТ способна была бы выполнить за полиномиальное. Жаль все-таки, что в реальности такая машина невозможна. Зато этот воображаемый компьютер позволил нам вплотную подобраться к одной из важнейших нерешенных проблем теории алгоритмов и математики в целом – так называемой проблеме равенства классов P и NP. Премия в миллион долларов обещана Математическим институтом Клэя тому, кто первым сумеет предложить доказуемо корректное решение[20]. P и NP – названия, присвоенные двум множествам задач разного класса сложности. Задачи множества P (от англ. polynomial – “полиномиальный”) могут быть решены за полиномиальное время на обычной (детерминированной) машине Тьюринга. Задачи множества NP (от англ. non-deterministic polynomial – “недетерминированный полиномиальный”) – это те, которые мы могли бы решить за полиномиальное время, будь у нас НМТ. (Одна из таких задач – разложение больших чисел на простые сомножители. НМТ способна выполнить поиск нужного множителя в двоичном дереве быстро, за полиномиальное время, тогда как ДМТ придется прочесывать каждую ветвь, что займет экспоненциальное время.) Это означает, что все задачи множества P принадлежат также и множеству NP, поскольку НМТ может делать все то же, что и обычная машина Тьюринга, за то же время.

Разумно предположить, что множество 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 – метода криптографической защиты (мы еще поговорим о нем позже), на который мы полагаемся ежедневно, например, при получении банковских услуг. Хотя, скорее всего, такого алгоритма все же не существует.