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

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

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

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

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

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

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