У всех машин Тьюринга, о которых мы говорили до сих пор, есть общая черта. В их алгоритмах – списках команд, указывающих им, что делать, – для каждой ситуации предусматривается только одно действие. Такие машины Тьюринга называются детерминированными (ДМТ). Получив команду, они автоматически ее выполняют: они неспособны “выбирать” между двумя различными командами. Но возможно представить себе и другой тип машин – недетерминированные (НМТ). В них каждая комбинация входных данных и состояния головки чтения-записи допускает выполнение более чем одной команды. НМТ – всего лишь мысленный эксперимент, построить ее в реальности было бы невозможно. Программа НМТ, например, могла бы включать как команду “Если текущее состояние 19 и обозреваемая ячейка содержит символ «1», нужно заменить его на «0» и перейти на одну ячейку вправо”, так и команду “Если текущее состояние 19 и обозреваемая ячейка содержит символ «1», нужно оставить его без изменений и перейти на одну ячейку влево”. В этом случае внутреннее состояние машины и символ на ленте не предусматривают единственно возможного действия. Вопрос: как же машина определяет, какое действие нужно выполнить?
НМТ изучает все возможные варианты решения задачи, а затем выбирает из них правильный (если он есть). Можно, конечно, считать такую машину просто исключительно везучим игроком, которому из множества решений всегда удается выбрать правильное. Но разумнее думать об НМТ как об устройстве, вычислительные способности которого возрастают по мере выполнения задачи таким образом, что каждый последующий шаг вычислений занимает не больше времени, чем предыдущий. Допустим, нужно выполнить поиск по двоичному дереву – структуре, в которой данные организованы таким образом, что в каждой точке (узле) происходит расщепление на два или более вариантов. Предположим, наша задача – найти в дереве конкретное число, скажем, 358. Машине нужно проходить каждый из всех возможных маршрутов до тех пор, пока она не найдет нужное число. Обычная машина Тьюринга, ДМТ, будет проходить их последовательно, один за другим, пока не наткнется на искомое значение. Поскольку количество ветвей в дереве увеличивается экспоненциально, удваиваясь на каждом уровне, на поиск нужного узла потребуется безнадежно много времени, если только по счастливой случайности он не будет находиться на одной из ближайших ветвей. А вот с НМТ ситуация меняется радикально: на каждом уровне двоичного дерева производительность машины словно бы удваивается, поэтому поиск на каждом последующем уровне занимает ровно столько же времени, сколько и на предыдущем, сколько бы ни было в дереве узлов.
В принципе, при наличии достаточного времени ДМТ под силу любая задача, с которой может справиться НМТ. Загвоздка как раз в “достаточности” времени. Ту же самую задачу, которую ДМТ выполняет за экспоненциальное время, НМТ способна была бы выполнить за полиномиальное. Жаль все-таки, что в реальности такая машина невозможна. Зато этот воображаемый компьютер позволил нам вплотную подобраться к одной из важнейших нерешенных проблем теории алгоритмов и математики в целом – так называемой проблеме равенства классов 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). Это объясняет, почему не одно поколение математиков, в последнее время даже вооруженных компьютерами, сталкивалось с трудностями при поиске оптимальных решений для сложных маршрутов.
