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

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

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

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

V _x 3 _y (x + y = x), V _x V _y (x + y = y + x)A-(V _x 3 _y (x + y = y))

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

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

формула V _x 3 _y (x + y = x) запишется в виде V x l3 x l0(x l+ x 10 = x l) и т. д. М. Пресбургером было в 1930 г. доказано существование алго­ритма, который дает ответ на вопрос, является ли данное слово в ал­фавите Л₃ формулой арифметики Пресбургера (разумеется, основная задача, решаемая этим алгоритмом, состоит в различении синтакси­чески правильных формул, принимающих значение 1 и соответствен­но 0; слова, не являющиеся синтаксически правильными формулами, легко распознаются и отвергаются).

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

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

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

В доказательстве теоремы Фишера—Рабина вычислительные шаги соответствуют рассмотрению 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].

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

те С. Если использовать МТ вместо РАМ, то возникающие дополни­тельные затраты на переходы от одной ячейки ленты к другой мож­но сделать меньшими, чем |х| + Ср(|х|) при каждой битовой опера­ции. Таким образом, общее число тактов работы МТ не превзойдет р(|х|)(|х| + Ср(|х|)), и сложность вычислений на МТ будет ограниче­на полиномом р{п){п + Ср{п)).

Дата добавления: 2014-01-11