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

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

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

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

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