Компьютерра - Журнал «Компьютерра» № 6 от 14 февраля 2006 года

состояние 0:

прочесть то, что находится под головкой: если 0, перейти в состояние 1; если 1, перейти в состояние 2; если пусто, перейти в состояние СТОП;

состояние 1:

записать в текущую ячейку 1 и перейти в состояние 3;

состояние 2:

записать в текущую ячейку 0 и перейти в состояние 3;

состояние 3:

сдвинуть головку вправо и перейти в состояние 0.

Она бит за битом инвертирует двоичную строку, записанную на ленте (считаем, что изначально головка находится в крайней левой ячейке, с которой начинается запись числа), а когда строка заканчивается, заканчивает работу и программа.

Эта модель вычислений, получившая название машины Тьюринга, стала общепринятой (хотя Пост придумал свою модель на год раньше). На первый взгляд такой простой объект кажется недостаточным для того, чтобы описать все многообразие компьютерных архитектур, — но пока не известно ни одного алгоритма, который нельзя было бы реализовать на машине Тьюринга. В логике и информатике широко известно нестрогое утверждение (так называемый тезис Черча), которое гласит, что любой объект, отвечающий нашему интуитивному понятию алгоритма, можно реализовать в виде программы на машине Тьюринга. Контрпримеров к этому утверждению пока не обнаружено, и оно считается верным — хотя доказать его, разумеется, невозможно.

Теперь нам нужно научиться оценивать скорость работы различных алгоритмов, сравнивать их друг с другом. Один и тот же алгоритм будет на «Пентиуме» работать несравненно быстрее, чем на машине Тьюринга. Более того, процессор современного компьютера может получить данные из любой ячейки памяти, просто «заказав» соответствующей шине адрес ячейки. А единственной головке машины Тьюринга, чтобы добраться до далеких данных, нужно шаг за шагом пройти всю ленту… Неужели эти изменения не влияют на теоретические оценки времени работы алгоритма?

Разумеется, влияют. Однако во многих принципиальных вопросах теории вычислений, к которым относится и обсуждаемая нами проблема P=?NP, принято считать эквивалентными по сложности такие алгоритмы, время выполнения которых отличается друг от друга полиномиально — то есть на величину, не превосходящую Cn

, где n — объем входной информации («длина входа»), C и d — константы[Отметим, что в теории вычислений невозможно оценивать работу алгоритма иначе, как на бесконечных сериях задач. Для этого используется язык «больших и малых О», пришедший сюда из матанализа. Например, если говорят, что алгоритм выполняется за время O(n•log n) на данном множестве задач, это означает, что существует некоторая константа C, единая для этого множества задач и такая, что алгоритм решает каждую из них не больше, чем за C•n•log n операций, где n — объем начальных данных задачи]. Неформально говоря, в рамках этой теории любые алгоритмы, работающие с «полиномиальной скоростью», считаются быстрыми (хотя на практике время их работы может быть неприемлемо большим). Класс задач, для которых существуют алгоритмы, решающие их за время, полиномиальное от размера входа, и есть тот самый класс P, о котором идет речь в формулировке нашей проблемы.

К классу P принадлежат очень многие известные задачи, — каждый, кто открывал учебники по программированию, помнит, сколько там алгоритмов, работающих за полиномиальное время. В статье «Теория и практика сложности» («КТ» #603) я уже писал о том, что Леонид Хачиян доказал, что в классе P лежит даже кажущаяся неприступно сложной задача линейного программирования.

Однако понять, что такое P, — это еще цветочки. Труднее дать определение класса NP. Формально оно звучит так: это класс задач, которые решаются за полиномиальное время на так называемых недетерминированных машинах Тьюринга. Можно довольно наглядно охарактеризовать эти задачи, используя понятие машины с подсказкой, хоть это и потребует некоторых усилий.

Рассмотрим для примера задачу выяснения истинности высказывания «заданное число — составное» (то есть у него есть нетривиальные простые делители). Это вычислительно сложная задача (по крайней мере, считается таковой). Однако если нам дали подсказку — предложили кандидата на роль делителя данного числа, — то проверка правильности подсказки очень проста: достаточно по-школьному, в столбик, разделить число на предполагаемый делитель. Эта быстрая операция позволяет сразу заключить: если разделилось без остатка, значит, делитель найден и число действительно составное. В этом случае машина выдает ответ «да». Если же не разделилось — машина, по правилам игры, должна сказать «нет». Ее задача — не найти ответ, а проверить, верно ли, что данная ей подсказка — это правильный ответ. Машина имеет право ошибаться только в одну сторону: она может сказать «нет», если подсказка не подходит (но мы-то понимаем, что может подойти какой-нибудь другой делитель, просто именно этот оказался неправильным), но не имеет права принять неверную подсказку (сказать «да», если делитель-подсказка не делит данное число). Более того, если на самом деле ответ положительный, требуется, чтобы существовала подсказка, которую приняла бы машина (в нашем примере это условие выполнено). Итак, задача входит в класс NP, если существует машина Тьюринга, которая по данной ей подсказке сможет за полиномиальное время либо дать положительный ответ и не ошибиться, либо дать отрицательный ответ с возможной ошибкой; однако для каждого набора данных, ответ на который положителен, должна существовать подсказка, которую примет такая машина Тьюринга.