§ 31. Существование задач распознавания, не принадлежащих р. Связь моделей мт и рам

Возникает вопрос, существуют ли вообще задачи распознавания при­надлежности слов некоторому языку, разрешимые алгоритмически, но не принадлежащие Р. Один из первых примеров задачи такого ро­да в 1973 г. был обнаружен М. Фишером и М. Рабином. Этот пример связан с так называемой арифметикой Пресбургера. Рассматривают-

202

Глава 7. Сводимость

ся логические формулы, записанные с соблюдением обычных син­таксических правил с помощью некоторого числа переменных, зна­ков +, =, логических связок V, Л, ­ и скобок; при этом каждая пере­менная должна быть связана одним из кванторов V, 3, а множеством значений переменных является N. Каждая такая формула, трактуемая как утверждение о неотрицательных целых числах, имеет значение «истина» или «ложь» (1 или 0). Арифметика Пресбургера—это сово­купность всех истинных формул указанного вида. Так, формулы

V_x3_y(x + y = x), V_xV_y(x + y = y + x)A-(V_x3_y(x + y = y))

принадлежат арифметике Пресбургера, а формула V_x3_y(x + y = y) — нет. Как и ранее, мы будем использовать переменные, имеющие вид буквы x, за которой следует некоторое двоичное число (номер пере­менной). В алфавите

Л₃ = {x, 0,1, +, =, V, л, ­, V, 3, (,)}

формула V_x3_y(x + y = x) запишется в виде Vxl3xl0(xl+ x10 = xl) и т. д. М. Пресбургером было в 1930 г. доказано существование алго­ритма, который дает ответ на вопрос, является ли данное слово в ал­фавите Л₃ формулой арифметики Пресбургера (разумеется, основная задача, решаемая этим алгоритмом, состоит в различении синтакси­чески правильных формул, принимающих значение 1 и соответствен­но 0; слова, не являющиеся синтаксически правильными формулами, легко распознаются и отвергаются).

Теорема, доказанная в 1973 г. Фишером и Рабином, может быть сформулирована так (мы не приводим доказательства¹).

Теорема Фишера—Рабина. Существует константа c > 0 такая, что для любого алгоритма A, распознающего среди всех слов из Л₃ те, которые являются формулами арифметики Пресбургера, существует целое n₀ такое, что для любого n>n₀ найдется слово из Л* длины n, для работы с которым алгоритму A потребуется более 2^2cn вычис­лительных шагов.

Из теоремы Фишера—Рабина следует, что арифметика Пресбурге­ра как предикат на Л₃ не принадлежит классу Р.

В доказательстве теоремы Фишера—Рабина вычислительные шаги соответствуют рассмотрению MT в качестве модели вычислений.

С помощью модели МТ доказывается, например, и теорема о том, что если t(n) —вычислимая с помощью некоторой машины Тьюринга

См. [48].

§ 31. Существование задач распознавания, не принадлежащих р 203

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

Модель МТ, однако, выглядит избыточно затратной в сравнении с моделью РАМ в силу, например, того, что если некоторый сим­вол хранится в ячейке а ленты и для определения хода дальнейших вычислений надо сравнить этот символ с символом, расположенным в ячейке Ь, которая находится далеко от ячейки а, то передвижение головки машины Тьюринга из а в Ъ потребует большого числа так­тов работы и, следовательно, больших затрат, а в случае модели РАМ сверх самой операции сравнения здесь нет затрат вообще.

Приведем соображение, которое можно оформить в виде теоре­мы², показывающее, что если некоторые вычисления имеют поли­номиальную сложность при использовании РАМ, то они будут иметь полиномиальную сложность и при использовании МТ. Для просто­ты будем считать, что речь идет о преобразовании слов в алфавите Л = {0,1} и соответственно о битовой сложности вычислений. Будем также считать, что на каждое присваивание тратится некоторое учи­тываемое время, в том числе на присваивание вида а :=Ъ, при кото­ром не выполняется никаких сравнений и изменений бит. Это дает возможность предполагать, что для сложности Т{п) по числу битовых операций произвольного алгоритма и его пространственной сложно­сти S{n), измеряемой числом используемых дополнительных ячеек, в худшем случае выполняется соотношение S{n)^C -Т{п) при неко­торой положительной константе С.

Пусть f :Λ^∗ →Λ и f_P мощью РАМ, имеющий

_M—некоторый алгоритм вычисления / с по­битовую сложность Тс (п), которая полино-

/рам ^ч

миально ограничена по длине п = \х\ входа х (считаем, что в каж­дой ячейке РАМ размещается 0 или 1). Пусть 7> (.п)<р(.п), где р — некоторый полином. Тогда количество ячеек, используемых /_РАМ при работе со словом х, сверх тех, в которых изначально хранит­ся х, не превосходит Ср(|х|) при некоторой положительной констан-

!См., например, [37, разд. 2], [4, разд. 4.2]. Впервые эта теорема была доказана, вероятно, М. Блюмом. ² См. [5, разд. 1.7].

204