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

Алгоритму вроде АКС, при условии что время выполнения операций выражается размером входных данных, возведенным в двенадцатую степень, на проверку простоты семидесятизначного числа потребуется “всего лишь” 14 миллионов секунд, или 160 дней. Это, конечно, все равно очень долго для скоростного компьютера, но по сравнению с астрономическим сроком, которого требует экспоненциальный алгоритм, почти молниеносно. Полиномиальные алгоритмы не всегда удобны на практике, но экспоненциальные при большом размере входных данных абсолютно неприемлемы. К счастью, есть целый ряд алгоритмов, занимающих промежуточное положение, и зачастую алгоритмы, которые работают “почти полиномиальное” время, достаточно практичны.

У всех машин Тьюринга, о которых мы говорили до сих пор, есть общая черта. В их алгоритмах – списках команд, указывающих им, что делать, – для каждой ситуации предусматривается только одно действие. Такие машины Тьюринга называются детерминированными (ДМТ). Получив команду, они автоматически ее выполняют: они неспособны “выбирать” между двумя различными командами. Но возможно представить себе и другой тип машин – недетерминированные (НМТ). В них каждая комбинация входных данных и состояния головки чтения-записи допускает выполнение более чем одной команды. НМТ – всего лишь мысленный эксперимент, построить ее в реальности было бы невозможно. Программа НМТ, например, могла бы включать как команду “Если текущее состояние 19 и обозреваемая ячейка содержит символ «1», нужно заменить его на «0» и перейти на одну ячейку вправо”, так и команду “Если текущее состояние 19 и обозреваемая ячейка содержит символ «1», нужно оставить его без изменений и перейти на одну ячейку влево”. В этом случае внутреннее состояние машины и символ на ленте не предусматривают единственно возможного действия. Вопрос: как же машина определяет, какое действие нужно выполнить?

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

В принципе, при наличии достаточного времени ДМТ под силу любая задача, с которой может справиться НМТ. Загвоздка как раз в “достаточности” времени. Ту же самую задачу, которую ДМТ выполняет за экспоненциальное время, НМТ способна была бы выполнить за полиномиальное. Жаль все-таки, что в реальности такая машина невозможна. Зато этот воображаемый компьютер позволил нам вплотную подобраться к одной из важнейших нерешенных проблем теории алгоритмов и математики в целом – так называемой проблеме равенства классов P и NP

. Премия в миллион долларов обещана Математическим институтом Клэя тому, кто первым сумеет предложить доказуемо корректное решение[20]. P и

NP – названия, присвоенные двум множествам задач разного класса сложности. Задачи множества P (от англ. polynomial

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