WWW.DOC.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Различные документы
 

«Магистерская программа «Математическое и программное обеспечение защиты информации» Магистерская диссертация О синтаксическом ...»

Центр

сертифик

ации

Московский государственный университет имени М.В. Ломоносова

Факультет вычислительной математики и кибернетики

Магистерская программа

«Математическое и программное обеспечение защиты информации»

Магистерская диссертация

О синтаксическом определении класса языков,

распознаваемых недетерминированными программами на

логарифмической памяти.

Работу выполнил

студент Носов Дмитрий Андреевич

Научный руководитель:

Варновский Николай Павлович Москва Содержание 1 Введение 4 2 Постановка задачи 6 3 Классы языков, распознаваемых недетерминированными программами из класса P R+ 7

3.1 Сигнатура недетерминированных программ.............. 7 Синтаксис класса недетерминированных программ P R+.......

3.2 7

3.3 Семантика недетерминированных программ.............. 8

3.4 Примеры недетерминированных программ............... 12 Класс Z+..................................

3.5 14 Класс Z+..................................

3.6 15 4 Вычислительные задачи на группоидных деревьях 28

4.1 Постановка задачи об определении принадлежности к подгруппоиду 28

4.2 Простое группоидное дерево....................... 31

4.3 Сложное группоидное дерево....................... 35



4.4 Квазигруппа сложного группоидного дерева.............. 36 5 Классы программ P R0 и P R 38 Класс программ P R0...........................

5.1 38

5.2 Программы с оператором недетерминированного выбора...... 39 Синтаксис класса недетерминированных программ P R.

–  –  –

В работах М. А. Тайцлина и А. П. Столбоушкина был введен один класс недетерминированных программ, определен класс языков, распознаваемых недетерминированными программами, и доказана теорема, свидетельствующая о близости этого класса, и NL. Мы исследуем классы языков, определяемые в некоторых модификациях указанной вычислительной модели. Для одного из введенных классов доказано, что он равен NL. Некоторый, предположительно более узкий, класс отделен от P.

1 Введение Мы предполагаем, что читатель знаком с понятиями машины Тьюринга, входа, времени работы, и памяти, в которой работает машина Тьюринга, а также со сложностными классами P и PSPACE. Говорят, что язык L принадлежит сложностному классу NL, если существует недетерминированная машина Тьюринга, которая распознает язык L в логарифмической от длины входа памяти.

Изначально проблема, совпадают ли сложностные классы NL и P, была сформулирована в работах С. Кука [1], [2], [3]. В этих работах доказаны утверждения, называемые, соответственно, первой, и второй теоремой Кука.

В обеих теоремах Кука рассматривается машина Тьюринга, работающая на входе длины n, и S(n) функция, которая мажорирует двоичный логарифм от n.

Первая теорема Кука утверждает, что класс языков, распознаваемых на детерминированной машине Тьюринга за время 2cS(n), где c любая положительная константа, распознается также детерминированными многоленточными машинами Тьюринга со стэком, память которых ограничена S(n). Эта теорема не доказывает совпадение классов NL и P, именно из-за наличия стэка неограниченного размера. Не получается доказать никаких соотношений между классами языков, распознаваемых машинами Тьюринга со стэком, классов NL и P.

Вторая теорема Кука, утверждает, что язык, который распознается недетерминированной односторонней многоленточной машиной Тьюринга со стэком, память которой ограничена S(n), распознается также недетерминированной односторонней многоленточной машиной Тьюринга без стэка, за время 2cS(n), где константа c не зависит от длины входа машины Тьюринга.

Понятие синтаксической характеризации впервые было подробно рассмотрено в [4].

Иммерман доказал, что NL = coNL (см. [5]).

Теорема Савича утверждает, что NL L2, где L2 класс языков, распознаваемых детерминированными машинами Тьюринга, работающими на квадратичной от логарифма длины входа памяти (см. [6]).

Подробнее о сложностных классах можно узнать в [7] и [8].

Определение класса недетерминированных программ P R+ было дано в работах [9] и [10]. Авторы доказали, что класс языков, распознаваемых недетерминированными программами из P R+ совпадает с NL LM, где LM все языки, являющиеся кодами универсальных алгебр. Насколько нам известно, полное доказательство этой теоремы не опубликовано. Данная теорема свидетельствует о том, что сложностной класс NL близок к классу языков, распознаваемых недетерминированными программами из P R+. В работах [11] и [12] рассматривались различные конструкции, основанные на недетерминированных программах. Однако вопрос, можно ли модифицировать модель вычислений основанную на недетерминированных программах таким образом, чтобы сложностной класс NL совпадал с классом языков, распознаваемых недетерминированными программами, оставался открытым. В диссертации на этот вопрос дается положительный ответ. В классе P R+ выделяется специальный подкласс недетерминированных программ.

Для этого подкласса дается новое определение языка, распознаваемого недетерминированной программой. Пусть Z+ класс всех таких языков. В диссертации доказано, что NL = Z+.

И.В. Попов предложил следующий подход к исследованию недетерминированных программ. Он ввел класс программ P R, исключив оператор инкремента из синтаксиса недетерминированных программ, но добавив оператор недетерминированного выбора. Полученный класс языков, предположительно, уже чем NL, однако точных оценок для него пока не получено. В диссертации предлагается несколько вариантов ограничений на программы из класса P R. Класс языков, соответствующие классу программ с наложенными ограничениями, отделен от P.

В диссертации предложена переформулировка задачи распознавания, решаемой недетерминированной программой, на языке совместности систем уравнений и неравенств.

Сложностной класс NL важен также для математической криптографии. В работах [13], [14] рассматривается модель противника, ограниченного логарифмической памятью.

2 Постановка задачи

Цели диссертации:

1. исследовать модификации определения класса языков, распознаваемых недетерминированными программами, с целью сближения этого класса с классом NL;

2. провести анализ ослабленных моделей вычислений, основанных на понятии недетерминированной программы. Сузить класс языков, распознаваемых такими программами, и отделить его от класса P.

Поставленные цели представляют интерес в связи со знаменитой проблемой о соотношении классов NL и P.

3 Классы языков, распознаваемых недетерминированными программами из класса P R+

3.1 Сигнатура недетерминированных программ

–  –  –

Количество переменных в программе конечно, фиксировано, и равно мощности множества X.

Заметим, что x = x + 1; это оператор недетерминированной программы, который в результате выполнения меняет значение переменной x на x. Семантика всех операторов будет рассмотрена ниже.

Определение 3.2.1. Для теста x = y?, где x, y переменные из X, x = y? это обратный тест. Мы будем обозначать обратный тест к T через !T. Аналогично, для теста x = y?, x = y? это обратный тест.

Определение 3.2.2. Класс недетерминированных программ P R+ это все недетерминированные программы всех сигнатур.

3.3 Семантика недетерминированных программ Определение 3.3.1. Путь вычислений конечная последовательность операторов и тестов.

По каждой недетерминированной программе можно построить не более чем счетное множество путей вычислений, которое однозначно определяет работу этой недетерминированной программы.

Построение будем осуществлять по индукции.

Через = {1, 2,...} обозначим множество путей вычислений недетерминированной программы P1 ; = {1, 2,...} это множество путей вычислений недетерминированной программы P2. i и i в данных обозначениях пути вычислений.

Определение 3.3.2. Множество путей вычислений программы P.

• Программе P, состоящей из одного оператора присваивания, инкремента или теста, соответствует множество путей вычислений программы P, в котором ровно один путь вычислений, состоящий из одного этого оператора(теста).





• Программе P, являющейся последовательной композицией программ, P = P1 ; P2 соответствует множество путей вычислений, состоящее из всех путей вычислений вида i ; j, для каждого i из и j из. Множества путей вычислений и недетерминированных программ P1 и P2 уже построены по индукции. Через i ; j мы обозначаем конкатенацию путей вычислений.

• Программе P, являющейся параллельной композицией программ, P = P1 P2 соответствует множество путей вычислений являющееся объединением (в теоретико-множественном смысле) множеств и. Как и в предыдущем случае, множества путей вычислений и недетерминированных программ P1 и P2 уже построены по индукции.

• Программе P, являющейся условным оператором вида if (Y) P1 endif соответствует объединение (в теоретико-множественном смысле) двух множеств путей вычислений:

–  –  –

• Программе P, являющейся оператором цикла while(Y) P1 endwhile соответствует счетное множество путей вычислений:

– !Y ; тест, обратный к Y.

–  –  –

Мы рассматриваем недетерминированные программы произвольной сигнатуры =, X.

Определение 3.3.3. Вход недетерминированной программы сигнатуры =, X это универсальная алгебра A сигнатуры.

Другими словами, вход недетерминированной программы это конкретные значения всех констант и функций сигнатуры недетерминированной программы.

Пусть i = (h1, h2,..., hk ) это некоторый путь вычислений из множества путей вычислений программы P ; каждый из ht это оператор или тест; универсальная алгебра A вход программы P.

–  –  –

• В начальный момент времени все переменные принимают значение 0, то есть s(0, x) = 0, для каждой переменной x.

• Пусть в момент времени t выполняется оператор x = f (x1,.., xk ). В этом случае s(t+1, x) = f (s(t, x1 ),.., s(t, xk )); s(t+1, y) = s(t, y) для любой переменной y, не совпадающей с x; значение функции f определяется универсальной алгеброй A.

• ?x = y. В этом случае s(t + 1, x) = s(t, x) для любой переменной x.

• ?x = y. В этом случае s(t + 1, x) = s(t, x) для любой переменной x.

–  –  –

• x = c. В этом случае s(t + 1, x) = c; s(t + 1, y) = s(t, y) для любой переменной y, не совпадающей с x. Значение константы c определяется универсальной алгеброй A.

• x = x + 1. В этом случае s(t + 1, x) = s(t, x). Данное определение корректно в силу того, что операция по определению есть в каждой сигнатуре. Соответственно, если s(t, x) есть LAST, то s(t + 1, x) = s(t, x). В обоих случаях, s(t + 1, y) = s(t, y) для любой переменной y, не совпадающей с x.

Каждый из тестов в рассматриваемом пути вычислений, на входе A, может быть либо истинным, либо ложным.

Определение 3.3.5. Тест ?x = y истинен в рассматриваемом пути вычислений, на входе A, тогда и только тогда, когда s(t, x) = s(t, y).

Определение 3.3.6. Тест ?x = y ложен в рассматриваемом пути вычислений, на входе A, тогда и только тогда, когда s(t, x) = s(t, y).

Истинный тест мы также будем называть выполненным.

Недетерминированная программа, также как и машина Тьюринга– распознаватель либо принимает вход, или не принимает.

Определение 3.3.7. Недетерминированная программа P принимает вход A, если существует путь вычислений i, из множества путей вычислений P, при работе которого на A, все тесты в i истинны.

3.4 Примеры недетерминированных программ Рассмотрим несколько простых примеров недетерминированных программ.

Программа, определяющая четность числа.

Утверждение 3.4.1. Существует недетерминированная программа из класса P R+, работающая на множестве A, с выделенной константой a, в которой все тесты истинны тогда и только тогда, когда константа a четна в заданной нумерации множества A.

Доказательство. Код программы:

x = 0;

if (x! = a) x! = LAST;

while(x! = a) x = x + 1;

x! = LAST?;

x + +;

if (x! = a) x! = LAST?;

endif endwhile Покажем, что данная программа действительно выполнена тода и только тогда, когда a четно.

Пусть a четно. тогда существует такое k, что a = 2k.

Индукцией по k покажем, что существует путь вычислений принимающий a, в котором тело цикла выполнялось k раз. При k равном 0, x = 0, тест на второй строке не выполнен и искомый путь вычислений x = 0; x = a? Пусть для k утверждение верно. Тогда существует путь вычислений 1,.., k, принимающий a 2. Здесь соответствует части программы до цикла, i i итерация цикла с истинной веткой условного оператоора, а i i итерация цикла с ложной веткой условного оператора. Рассмотрим путь вычислений 1,.., k ; k+1 После выполнения k итерации цикла x = a 2, далее тест x! = a истиннен, после x + +;

переменная x принимает значение a 1, тест x! = LAST ? истиннен, после x + +;

переменная x принимает значение a, условный оператор ложен, и искомый путь вычислений найден.

Пусть a нечетно. тогда начиная с некоторого момента в каждом более длинном пути вычислений будет ложный тест на сравнение x и LAST, что и требуется.

Программа, проверяющая, что N 3.

Утверждение 3.4.2. Существует недетерминированная программа из класса P R+, работающая на множестве A, в которой все тесты истинны тогда и только тогда, когда в множестве A больше 3 элементов.

Доказательство. Программа, решающая данную проблему:

x = RAND;

y = RAND;

z = RAND;

t = RAND;

x! = y?

x! = z?

x! = t?

z! = y?

t! = y?

t! = z?

Покажем, что данная программа действительно выполнена тода и только тогда, когда N 3.

Пусть N 3. Тогда существует набор из 4 различных элементов, который будет присвоен переменным x, y, z, t.

При этих значениях все тесты истинны, что и требуется.

Пусть N 3. Тогда не существует набора из 4 различных элементов.

Соответственно, при любых значениях переменных x, y, z, t будут по крайней мере две переменные, принимающие одинаковые значения. А это значит, что один из тестов будет ложен, что и требуется.

–  –  –

• разделитель #;

• значения констант c1, c2,..., cn1, в унарной системе счисления, разделенные специальным символом %;

Определение 3.5.1. LM это множество слов, каждое из которых кодирует какую-либо универсальную алгебру сигнатуры.

Определение 3.5.2. LM это множество, элементами которого являются все возможные подмножества всех множеств LM, для всех возможных сигнатур.

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

Определение 3.5.3.

Недетерминированная программа P сигнатуры =, X распознает язык L в алфавите {|, 0, #, 1}, если выполнено следующее условие:

w L тогда и только тогда, когда

1. w является кодом некоторой конкретной универсальной алгебры A сигнатуры, то есть w LM ;

2. недетерминированная программа P принимает вход A.

Определение 3.5.4. Класс языков Z+ это все языки, распознаваемые недетерминированными программами из класса P R+.

Справедлива следующая теорема, авторами которой являются М. А. Тайцлин и А. П. Столбоушкин, [9].

–  –  –

В классе Z+, в отличие от класса Z+, рассматриваются недетерминированные программы фиксированной сигнатуры. Зафиксируем сигнатуру = 0, LAST, a, b, err,, f (1). =, X. X, как и ранее конечное множество переменных недетерминированной программы; 0, LAST, a, b, err константы.

–  –  –

• значения констант err, a, b это, соответственно, элементы err, a, b носителя универсальной алгебры.

Определение 3.6.3. Код универсальной алгебры A A() это слово w длины N + 1 в алфавите {a, b}, такое, что на i-ой позиции в слове w стоит значение f (i).

N это мощность носителя A.

Утверждение 3.6.1. Существует взаимно однозначное соответствие кодов A() и слов в алфавите {a, b}.

Доказательство. Очевидно следует из того, что каждая универсальная алгебра из A() однозначно характеризуется значениями своей функции f.

Утверждение 3.6.2. Множество кодов универсальных алгебр A() это все слова в алфавите {a, b}.

Доказательство. Это утверждение является следствием утверждения 3.6.1.

–  –  –

Доказательство. Доказательство теоремы взято из [17].

Всюду далее, без ограничения общности, будем считать, что рассматриваемая машина Тьюринга начинает работу в состоянии q0, и имеет два заключительных qacc и qrej. В случае, если машина Тьюринга принимает слово, засостояния писанное на входной ленте, то существует конечная последовательность команд, применяя которые машина перейдет в состояние qacc. В противном случае машина Тьюринга зацикливается, или переходит в qrej. У нескольких команд машины Тьюринга может быть одинаковая левая часть, в этом случае на исполнение будет недетерминированно выбрана одна из этих команд.

В доказательстве мы не будем рассматривать случай, когда слово w пусто. В этом, и только в этом случае входная лента машины Тьюринга пуста. В этом, и только в этом случае носитель универсальной алгебры A состоит только из {err, a, b}; значения констант 0, LAST программы P равны err; а также для любого i f (i) = err. Длины всех рабочих лент в этом случае ограничены константой.

1. Докажем, что Z+ NL.

Пусть L Z+, P + недетерминированная программа из класса P R, распознающая этот язык. Это значит, что для каждого слова w L существует универсальная алгебра A из A(), такая что w является кодом A, и P принимает вход A. Нам необходимо доказать, что L NL. Для этого достаточно построить недетерминированную машину Тьюринга M, работающую в логарифмической памяти с одной входной и несколькими рабочими лентами, которая принимает все слова w L, и только их.

Количество рабочих лент машины M в данном доказательстве зависит от количества переменных в недетерминированной программе.

Точное число рабочих лент:

• по одной рабочей ленте для каждой переменной недетерминированной программы,

• одна рабочая лента для выполнения оператора функционального присваивания,

• по одной ленте для каждой константы.

До начала работы машины M на входной ленте записано слово w, все рабочие ленты пусты. На всех лентах машины Тьюринга мы будем использовать заранее фиксированный алфавит.

Утверждение 3.6.3. Значение любой переменной программы P может быть записано на одной рабочей ленте.

Доказательство. Рассмотрим слово w длины N + 1, записанное на входной ленте машины M. Носитель универсальной алгебры A = {err, a, b, 0,..., N }. Каждая из переменных недетерминированной программы P может принимать значение от 0 до N, а также значения a, b, err. На входной ленте машины M записано ровно N + 1 символов, а длина рабочей ленты ограничена логарифмом от длины входа, следовательно, любое значение переменной недетерминированной программы может быть записано в двоичной системе счисления на любой рабочей ленте.

Пусть в рассматриваемой недетерминированной программе k переменных, тогда текущее состояние всех переменных может быть записано на k рабочих лентах машины Тьюринга.

До начала выполнения программы, все переменные принимают значение 0, соответственно на каждой рабочей ленте, отвечающей за соответствующую переменную, записано значение, соответствующее 0. В начале работы машина Тьюринга M запишет на специальные рабочие ленты значения констант недетерминированной программы, в том числе констант 0, LAST, err.

В ходе доказательства мы сначала построим машины Тьюринга, которые соответствуют операторам недетерминированной программы. Эти ”базисные” машины изменяют состояние рабочих лент, и переходят в свое состояние qacc, когда моделирование оператора недетерминированной программы завершено. Когда моделируются тесты недетерминированной программы, то соответствующая ”базисная” машина Тьюринга переходит в qacc, или в qrej.

Далее мы рассмотрим, как построить машины Тьюринга, соответствующие более сложным программам, по индукции. Эти построения будут осуществляться, в основном, изменением состояния машины Тьюринга, и не будут менять ее рабочие ленты.

Следующее утверждение является базисом индукции по сложности программы.

Утверждение 3.6.4. Если программа P состоит из одного оператора, то соответствующая ”базисная” машина Тьюринга M существует.

Доказательство. Рассмотрим все возможные программы из одного оператора.

• P = x = f (y); оператор присваивания. В этом случае, соответствующая машина M должна записать на ленту, соответствующую переменной x, значение функции f от y. Напомним, что слово, кодирующее функцию f записано на входной ленте. Для выполнения данного оператора нам понадобится дополнительная рабочая лента, которая, как и все ленты, ограничена логарифмом от длины входа. Машина M смещается по входной ленте, соответствующей данной функции, на y ячеек. Для этого используется дополнительная лента. Далее необходимо присвоить значение a или b, в зависимости от обозреваемого символа на входной ленте, переменной x. Для этого надо скопировать значение, соответствующее a или b, хранящееся на специальной рабочей ленте, на ленту соответствующую переменной x. После этого машина Тьюринга M переходит в заключительное состояние qacc.

• P = x = x + 1; оператор инкремента. В этом случае, соответствующая машина M должна прибавить единицу в двоичной системе счисления на ленте, соответствующей переменной x, и перейти в заключительное состояние qacc.

• P = x = y; оператор присваивания. В этом случае, соответствующая машина M должна скопировать ленту, соответствующую переменной y, на ленту, соответствующую переменной x, и перейти в заключительное состояние qacc.

• P = x = c; оператор присваивания. В этом случае, соответствующая машина M должна скопировать ленту, соответствующую константе c, на ленту, соответствующую переменной x, и перейти в заключительное состояние qacc.

• P = x = y? положительный тест. В этом случае, соответствующая машина M должна удостовериться, что ленты, соответствующие переменным x и y совпадают. Иными словами, если ленты совпадают, соответствующая машина M переходит в состояние qacc, а если не совпадают то в qrej.

• P = x = y? отрицательный тест. В этом случае, соответствующая машина M должна удостовериться, что ленты, соответствующие переменным x и y различны хотя бы в одном символе. Иными словами, если ленты совпадают соответствующая машина M переходит в состояние qrej, а если не совпадато в qacc.

ют Следующее утверждение является шагом индукции по сложности программы.

Утверждение 3.6.5. Если программа P является композицией программ, ветвлением, или циклом, и машины Тьюринга, моделирующие составные части программы P, существуют, то существует машина Тьюринга M, моделирующая программу P.

Доказательство.

Определение 3.6.6. Безусловный переход из состояния q1 в состояние q2 машины Тьюринга M это переход из состояния q1 в состояние q2, при котором не происходит движения головок машины Тьюринга по лентам, не происходит изменения рабочих лент, и который происходит при любых символах, которые читаются в текущий момент головками машины Тьюринга.

Введем условные обозначения: машину Тьюринга, соответствующую недетерминированной программе P1 мы обозначим через M1 ; машину Тьюринга, соответствующую недетерминированной программе P2 мы обозначим через M2 ; машину Тьюринга, соответствующую тесту Y мы обозначим через MT ; результирующую машину Тьюринга мы будем обозначать через M. Здесь недетерминированные программы P1 и P2 это составные части программы P.

• P = P1 ; P2 последовательная композиция программ P1 и P2. В этом случае результирующая машина M делает безусловный переход из qacc машины Тьюринга M1 в начальное состояние машины Тьюринга M2, и безусловный переход из qrej машины Тьюринга M1 в qrej машины Тьюринга, соответствующей P2 (M2 ). Начальным состоянием результирующей машины M будет начальное состояние M1 ; заключительными заключительные состояния M2.

Далее необходимо преобразовать полученную машину, чтобы в ней было одqacc и qrej.

но входное состояние, и два заключительных

• P = if (Y) P1 endif ветвление. Начальным состоянием результирующей машины M будет начальное состояние машины MT ; заключительными состозаключительные состояния M1. Также в результирующей машине яниями M есть безусловный переход из qacc машины MT в начальное состояние M1, и безусловный переход из qrej машины MT в qacc машины M1.

• P = P1 P2 параллельная композиция программ. Введем новые состояначальное и два заключительных для машины M. В результирующей ния машине M будут следующие безусловные переходы:

1. из начального состояния машины M в начальное состояние M1 ;

2. из начального состояния машины M в начальное состояние M2 ;

–  –  –

4. из qacc машины MT в начальное состояние машины M1 ;

5. из qacc машины M1 в начальное состояние машины MT ;

На этом построение машины Тьюринга M завершено.

Лемма 2.1.

Если программа P приняла вход w, то машина Тьюринга M принимает вход w.

Доказательство. Если программа P приняла вход w, то в ней существует путь вычислений i, при работе которого на входе w, все тесты в нем истинны. Машина Тьюринга M принимает вход w тогда и только тогда, когда в ней есть ветвь вычислений, завершающаяся в состоянии qacc.

Рассмотрим ветвь вычислений y машины Тьюринга, соответствующую этому пути вычислений i. В этой ветви вычислений все циклы отработают в точности столько же раз, как и в i ; все операторы параллельной композиции будут работать так же, как и в i. В результате ветвь вычислений y, после выполнения каждого блока команд, соответствующих одному оператору, будет моделировать состояние i. Но это значит, что, так как все тесты в i истинны, в ветви вычислений y все блоки команд, соответствующих одному оператору, будут завершаться в промежуточном состоянии qacc. А значит, и вся ветвь y целиком завершится в состоянии qacc, что и требуется.

Лемма 2.2.

Если программа P не принимает вход w, то и машина Тьюринга M не принимает вход w.

Доказательство. Машина Тьюринга M не принимает вход w тогда и только тогда, когда в M нет ни одной ветви вычислений, завершающаяся в состоянии qacc.

Если программа P не приняла вход w, значит каждый путь вычислений в ней либо бесконечен, либо содержит ложный тест.

Будем проводить доказательство от противного пусть некоторая ветвь вычислений y машины M завершается в состоянии qacc. Заметим, что, по построению машины M, переход из промежуточного состояния qrej в состояние qacc возможен только в цикле. Построим путь вычисления y по ветви вычислений y. Он конечен. Так как y закончилась в состоянии qacc, то в y нет ни одного теста, который ложен. Но существование такого пути вычислений невозможно по исходному предположению. Из этого следует, что если программа P не принимает вход w, то и машина Тьюринга M не принимает вход w.

2. Докажем, что NL Z+.

Пусть язык L NL. Это значит, что язык L распознается машиной Тьюринга M, работающей в логарифмической памяти. Нам необходимо построить недетерминированную программу P из класса P R, которая распознает этот язык L.

Без ограничения общности можно считать, что моделируемая машина Тьюринга M имеет одну входную ленту, одну рабочую ленту, каждая лента машины Тьюринга является полубесконечной, и длина используемой части рабочей ленты ограничена константой, умноженной на логарифм от длины входной ленты.

Благодаря этой константе нам не важно основание логарифма.

слово в алфавите {a, b}, которому однозначно соВход машины Тьюринга ответствует универсальная алгебра из A(), на которой работает недетерминированная программа.

При длине входа N, количество различных вариантов заполнения рабочей ленты равно 2logc N = N v, для некоторой константы v. logc в данных обозначениях длина используемой части рабочей ленты. Учитывая, что каждая переменная недетерминированной программы принимает значения от 0 до N 1 = LAST, а также a, b, err, с помощью v переменных недетерминированной программы можно закодировать рабочую ленту.

Количество состояний в машине Тьюринга конечно, следовательно их можно закодировать с помощью конечного числа переменных.

–  –  –

Определение 3.6.7. Кортеж переменных это последовательность переменных недетерминированной программы, кодирующая

• состояние машины Тьюринга;

• или состояние одной рабочей ленты машины Тьюринга;

• или позицию на входной ленте.

Обозначим кортеж, соответствующий состоянию q через xq. Кортеж, соответствующий текущему состоянию обозначим через xcurQ. Кортеж, соответствующий рабочей ленте обозначим work. Подчеркнем, что в программе нет кортежа, соответствующего входной ленте (но есть кортеж с позицией на входной ленте). Бутекущую позицию на входной ленте за posV. Позиция дем обозначать кортеж число, меньшее logc N и также может быть записана в одной на рабочей ленте переменной. Для единообразия, можно считать ее кортежем из одной переменной.

Будем обозначать позицию на рабочей ленте за posW.

Так как все операции осуществляются с кортежами переменных (разной длины), операции сравнения кортежей, добавления и вычитания единицы к кортежу являются элементарными подпрограммами.

Элементарные подпрограммы

При моделировании машин Тьюринга мы будем использовать следующие подпрограммы:

• Программа Input(i), выбирающая i-ый символ на входной ленте машины M.

• Программа W orkSymbol(w, i), вычисляющая i-ый символ на рабочей ленте, соответствующей кортежу w.

• Программа W riteSymbol(w, s, i), моделирующая запись символа s на i-ую позицию на рабочей ленте. Кортеж w при этом моделирует рабочую ленту.

• Программа Shif tInput(posV, d), выполняющая оператор i = i + d для счетчика, соответствующего входной ленте. d {1, 0, 1} это сдвиг.

• Программа Shif tW ork(posW, d), выполняющая оператор i = i + d для счетчика, соответствующего рабочей ленте. d {1, 0, 1} это сдвиг.

Определение 3.6.8. Подпрограмма это недетерминированная программа, которая является частью другой недетерминированной программы.

Лемма 2.3.

Каждая команда машины Тьюринга M может быть промоделирована подпрограммой.

Доказательство. Рассмотрим произвольную команду com машины Тьюринга.

Она имеет вид:

com = cq, ca, cb cq, cw, cs1, cs2, где

–  –  –

• ca символ, который машина Тьюринга наблюдает в текущий момент на входной ленте;

• cb символ, который машина Тьюринга наблюдает в текущий момент на рабочей ленте;

–  –  –

Как уже говорилось, несколько команд машины Тьюринга могут иметь одинаковую левую часть.

Каждая команда машины Тьюринга преобразуется в собственную подпрограмму.

В подпрограмме, соответствующей команде com машины Тьюринга M вначале проверяется, что

• кортеж текущего состояния xcurQ равен xcq, соответствующему состоянию cq из левой части команды com;

• на входной ленте в текущей позиции записан правильный символ, то есть Input(posV ) совпадает с ca;

• на рабочей ленте в текущей позиции записан правильный символ, то есть W orkSymbol(work, posW ) совпадает с cb.

Все эти проверки являются вложенными условными операторами.

Если все эти условия выполнены, то подпрограмма далее

• меняет кортеж состояния xcurQ на xcq ;

–  –  –

• меняет текущие позиции на входной и рабочей лентах (выполняя элементарные подпрограммы Shif tInput(posV, cs1 ) и Shif tW ork(posW, cs1 )).

Заметим, что подпрограмма, соответствующая одной команде машины Тьюринга, обладает следующим свойством: в этой программе все тесты выполнены тогда и только тогда, когда данная команда может быть применена, то есть выполнены все условия левой части команды. Это и означает, что подпрограмма моделирует команду машины Тьюринга.

Построение программы P, моделирующей машину Тьюринга M.

Далее все полученные таким образом программы P1,..., Pd, где d количество команд машины Тьюринга объединяются следующим образом: Пока текущее состояние моделируемой машины M не заключительное (то есть не qacc или qrej ), мы выполняем объединение всех подпрограмм, соответствующих командам машины Тьюринга.

(p = 0) while(p == 0) P1 P2... Pd if (xcurQ == xqacc )p = err;

endwhile.

На этом построение программы P завершено.

По определению, машина Тьюринга распознает некоторое слово тогда и только тогда, когда существует последовательность команд машины Тьюринга, переводящая ее в заключительное состояние qacc. В случае, если существует последовательность команд машины Тьюринга, переводящая ее в заключительное состояние, будет существовать и конечный путь вычислений, соответствующий данной последовательности команд.

Лемма 2.4.

Если машина Тьюринга M принимает вход w, то и программа P принимает вход w.

Доказательство. Если машина Тьюринга M принимает вход w, то в ней есть ветвь вычислений, завершающаяся в состоянии qacc. Если в программе P при работе на входе w есть путь вычислений, на котором все тесты истинны, то программа P принимает вход w. Соответственно, нам необходимо доказать, что если в исходной машине Тьюринга M была ветвь вычислений, завершающаяся в состоянии qacc, то в программе P при работе на входе w будет путь вычислений, на котором все тесты истинны.

Рассмотрим ветвь вычислений y, завершающаяся в состоянии qacc. Ей соответствует набор подпрограмм Pi1, Pi2,..., Pik, таких что Pij соответствует j-ой команде ветви y. Рассмотрим путь вычислений r, полученный последовательной композицией этих подпрограмм, однозначно определяемый по одной ветви вычислений M. В конец r добавим тест xcurQ = xqacc. Дополним путь вычислений r тестами p == 0, xcurQ = xqacc, между каждой из подпрограмм Pij и Pij+1. В результате r будет путем вычислений из множества путей вычислений итоговой программы P.

Докажем, что на r все тесты истинны.

• Все тесты в подпрограммах Pij истинны, так как они соответствуют условиям, при которых применялись команды ветви вычислений y машины Тьюринга M.

• Все добавленные тесты p == 0, xcurQ = xqacc истинны, так как при выполнении ветви вычислений y состояние машины Тьюринга равно qacc только после выполнения последней из команд ветви вычислений y, но не ранее.

• Добавленный тест xcurQ == xqacc истинен, так как в конце выполнения ветви вычислений y состояние машины Тьюринга действительно равно qacc.

Никаких других тестов в рассматриваемом пути вычислений нет, а, значит, программа P действительно принимает вход w.

Лемма 2.5.

Если машина Тьюринга M не принимает вход w, то и программа P не принимает вход w.

Доказательство. Если машина Тьюринга M не принимает вход w, то в ней нет ветви вычислений, завершающейся в состоянии qacc. Программа P не принимает вход w тогда и только тогда, когда в ней при работе на входе w нет ни одного пути вычислений, на котором все тесты истинны. Соответственно, нам необходимо доказать, что если в исходной машине Тьюринга M не было ветви вычислений, завершающейся в состоянии qacc, то в программе P при работе на входе w не будет ни одного пути вычислений, на котором все тесты истинны.

Пусть в исходной машине Тьюринга M не было ветви вычислений, завершающейся в состоянии qacc. Будем доказывать утверждение от противного. Предположим, что существует путь вычислений программы P, на котором все тесты истинны. По построению итоговой программы, чтобы выйти из цикла результирующей программы P, должен был быть истинным тест xcurQ == xqacc. Однако это значит, что в результате выполнения некоторого конечного набора подпрограмм Pi1, Pi2,..., Pik верно, что xcurQ == xqacc. По построению подпрограмм Pij, это значит, что в машине Тьюринга M существует ветвь вычислений, завершающаяся в состоянии qacc. Полученное противоречие доказывает утверждение.

4 Вычислительные задачи на группоидных деревьях В предыдущей главе мы получили достаточно общий результат о выразительной силе недетерминированных программ из класса P R+. Как уже было сказано во введении, долгосрочной целью исследований в данной области является разделение сложностных классов P и N L. В силу того что классы N L и Z+ равны, для

–  –  –

возможных подходов таков:

• зафиксировать алгебраическую систему A;

• определить язык L, являющийся кодом A;

• показать, что язык L распознается за полиномиальное время детерминированной машиной Тьюринга;

• доказать, что не существует недетерминированной программы из класса P R+, распознающей язык L.

В данной главе мы зафиксируем алгебраическую систему и вычислительную задачу, которую будем рассматривать в оставшейся части работы.

4.1 Постановка задачи об определении принадлежности к подгруппоиду

Мы будем рассматривать недетерминированные программы, работающие на группоиде, то есть алгебраическая система группоид. Обозначим этот группоид через A. Сигнатура системы имеет следующий вид:

= a, b, 0, LAST, f, где a и b константы, f двуместная функция.

Определение 4.1.1. Вычислительная задача G (об определении принадлежности к подгруппоиду): по заданным элементам a и b группоида A определить, принадлежит ли b подгруппоиду, порожденному a.

Ранее уже говорилось, что данной задаче соответствует конкретный язык L.

Слово w принадлежит языку L, если оно имеет следующий формат:

• константа a в унарной системе счисления;

• разделитель |;

• константа b в унарной системе счисления;

• разделитель |;

• таблица функции f, состоящая из N 3 нулей и единиц.

Утверждение 4.1.1. Язык L принадлежит сложностному классу P.

Доказательство. Необходимо доказать существование детерминированной машины Тьюринга, распознающей язык L за полиномиальное время. Искомая машина

Тьюринга:

1. Записывает элемент a на рабочую ленту;

2. Проверяет, что на рабочей ленте не записан элемент b, если записан, то слово принято;

3. Проверяет, записаны ли на рабочей ленте элементы x1 и x2, такие что f (x1, x2 ) не записан на рабочей ленте;

4. Если ответ в пункте 3 ДА, то элемент f (x1, x2 ) записывается на рабочую ленту, и алгоритм возвращается к пункту 2.

5. Если ответ в пункте 3 НЕТ, то слово не принято.

Полиномиальность данного алгоритма очевидна, так как пункты 2–4 могут повториться не более n раз, где n количество элементов в группоиде.

Определение 4.1.2. Мы будем говорить, что программа P выражает, что элемент b группоида A принадлежит подгруппоиду, порожденному элементом a, если:

1. в программе есть только константы a, b, 0, LAST ;

2. константа b не используется в присваиваниях;

3. последний оператор программы P тест ?z = b, причем других тестов в которых используется b нет;

4. если элемент b группоида A принадлежит подгруппоиду порожденному элементом a, то есть хотя бы один путь вычислений, в котором все тесты выполнены;

5. если элемент b группоида A не принадлежит подгруппоиду порожденному элементом a, то нет ни одного пути вычислений, в котором все тесты выполнены;

6. условия 4 и 5 выполняются для любого отображения множества констант в множество элементов группоида.

Определение 4.1.3. Вычислительная задача G(k) это задача G, при условии того, что мощность группоида A ограничена сверху k.

Утверждение 4.1.2. Существует недетерминированная программа, решает вычислительную задачу G(K) (для любого k).

Доказательство. В группоиде A k элементов. Тогда в искомой недетерминированной программе есть k выделенных переменных, и еще есть несколько вспомогательных переменных. Искомая недетерминированная программа:

1. Добавляет элемент a к выделенным;

2. Проверяет, среди выделенных элементов нет элемента b, если есть, то универсальная алгебра принята;

3. Проверяет, есть ли среди выделенных элементы x1 и x2, такие что f (x1, x2 ) не является выделенным элементом;

4. Если ответ в пункте 3 ДА, то элемент f (x1, x2 ) добавляется к выделенным, и алгоритм возвращается к пункту 2.

5. Если ответ в пункте 3 НЕТ, то слово не принято.

Замечание 1. Если количество элементов группоида задано заранее, то данная вычислительная задача решается машиной Тьюринга с константной памятью.

Замечание 2. Вычислительная задача G выбрана из-за того, что очевидный алгоритм требует большой памяти для своей работы.

4.2 Простое группоидное дерево Рассмотрим теперь группоид неограниченного размера.

Определение 4.2.1. Простое группоидное дерево это дерево, на котором введена структура группоида.

Носитель группоида это множество всех вершин дерева; операция f на этом группоиде определяется следующим образом:

–  –  –

Замечание 3. Далее мы иногда будем отождествлять элементы группоида и вершины дерева, поскольку между ними есть взаимно-однозначное соответствие.

Утверждение 4.2.1.

В простом группоидном дереве, подгруппоид порожденный элементом a:

• это сам элемент a, если элемент a не является листом.

• это поддерево, крайним левым листом которого является a, иначе.

Доказательство данного утверждение напрямую следует из определения.

Утверждение 4.2.2. Существует недетерминированная программа из класса P R+, проверяющая, что элемент a является листом, причем не крайним справа.

Доказательство. В этом и только в этом случае, f (a, a) = a.

Утверждение 4.2.3. Существует недетерминированная программа из класса P R+, которая по данному элементу t1 находит элемент t2 такой, что t2 является отцом t1.

Доказательство. Необходимо найти такой элемент t3, что t3 не равен t1, и f (t1, t3 )! = t1. Для этого достаточно перебрать все элементы группоида, проверяя несколько тестов.

Если такой элемент найден, то f (t1, t3 ) есть t2. Если такого элемента нет, то t1 корень дерева T.

Замечание 4. Развивая идею предыдущего доказательства покажем, что существует недетерминированная программа из класса P R+ проверяющая, что элемент a является корнем.

Код программы, которая определяет, лежит ли константа a в корне:

r=0 while(r == 0) y = 0;

while(y! = LAST) z = f (x, y);

y = y + 1;

ifz! = x y = LAST;

endif ;

endwhile;

ifz == x r = LAST;

endif ;

x = z;

endwhile;

z == a?

Утверждение 4.2.4. Данная недетерминированная программа принимает группоидное дерево A и константу a тогда и только тогда, когда a лежит в корне дерева, соответствующего A.

Доказательство. Перед последним тестом в переменной z будет находиться элемент группоида. Докажем, что данный элемент лежит в корне дерева T. От противного. Пусть после окончания программы в переменной х находится значение, не лежащая в корне дерева. Так как цикл по r завершился, то переменная r не равна 0. Это значит, что, так как в программе есть только одно место, где меняется переменная r, в условном операторе переменная z совпадала с переменной x.

Следовательно, цикл по y закончился из-за невыполнения условия y! = LAST, то есть переменная y по очереди принимала каждое значение от 0 до LAST, причем в каждом случае было не выполнено условие z = x. То есть f (x, y) равна x для любого y. Это возможно только для корня дерева.

Утверждение 4.2.5. Существует недетерминированная программа из класса P R+, которая по данным двум элементам t1 и t2, находит элемент t3 такой, что f (t1, t3 ) = t2.

Доказательство. Искомая недетерминированная программа перебирает все элементы группоида от 0 до LAST, и проверяет, выполнен ли тест из условия.

x = 0;

r = 0;

while(x! = LAST) t = f (t1, x);

if (t == t2 ) r = x;

endif ;

endwhile;

Утверждение 4.2.6. Существует недетерминированная программа из класса P R+, решающая задачу G на простом группоидном дереве.

Доказательство. В данном доказательстве мы отождествляем элементы группоида и вершины дерева, поскольку между ними есть взаимно-однозначное соответствие. Сначала надо проверить, что элемент a является листом, причем не крайним справа. Если это не так, то подгруппоид, порожденный a содержит только a, и задача сводится к одному тесту. Данная проверка возможна в силу утверждения 4.2.2. Через p(x) обозначим отца вершины x; через li i-ый лист в дереве. Пусть a i-ый лист (т.е. li ), являющийся правым сыном своего родителя. Тогда, с точностью до a, подгруппоид порожденный a совпадает с подгруппоидом, порожденным i + 1-ым листом (правым соседом a). Рассмотрим случай, когда a i-ый лист (т.е.

li ), являющийся левым сыном своего родителя. Будем перебрать li, li+2, li+4 и т.д.

листы. Для каждого из них построим последовательность отцов. Например, для li мы последовательно построим p(li ), p(p(li )), p(p(p(li ))) и т.д. Заметим, что для такого построения нам не нужно много переменных: необходима одна переменная для текущего листа, одна для текущего отца в последовательности, и несколько вспомогательных переменных для вычислений. Совокупность построенных последовательностей есть в точности все вершины поддерева, крайним левым листом которого является a, а следовательно, и все элементы подгруппоида, порожденного a, что и требуется.

Код программы, которая определяет, принадлежит ли константа b подгруппоиду, порожденному a (в случае простого группоидного дерева):

r=0 w=0 x=a z=a while(r == 0) y = 0;

while(y! = LAST) ify == x y = y + 1;

endif ;

z = g(x, y);

y = y + 1;

ifz! = x y = LAST;

endif ;

endwhile;

ifz == x r = LAST;

endif ;

ifb == x w = LAST;

endif ;

x = z;

endwhile;

w == LAST?

Докажем корректность данной программы. В данной программе есть только один тест, поэтому она выполнена тогда и только тогда, когда последний тест истиннен. Последний тест истиннен тогда и только тогда, когда то переменная w меняла свое значение в процессе работы программы. Последнее верно тогда и только тогда, когда в процессе работы программы тест b == x был истиннен. Константа b по ходу программы не меняется (по определению константы). Значение переменной x меняется только в одном месте оператор x = z;.

Необходимо доказать, что переменные z и x по ходу выполнения программы принимют только значения из подгруппоида порожденного константой a.

Индукция по циклу по r:

В начале выполнения программы переменным z и x присваивается константа a это базис.

Шаг индукции. Значение переменной z меняется только в одном месте оператор z = g(x, y);. Так как переменная x по ходу выполнения программы принимют только значения из подгруппоида порожденного константой a (по индукционному предположению), то в случае, если после выполнения этого оператора переменная z приняла значение переменной x, утверждение верно.

Если же значение переменной z изменилось, то оно изменилось по правилу (1) на вышележащее в дереве, так как в программе перед выполнением опратора проверяется тест на равенство переменных x и y. Выше мы показали, что программа такого типа проверяет все дерево до корня, а значит, каждый элемент подгруппоида, порожденного константой a будет проверен в программе.

4.3 Сложное группоидное дерево

Предыдущее утверждение свидетельствует о том, что недетерминированные программы обладают достаточной выразительной силой, чтобы решать задачу G на ”просто” устроенном группоиде. Программа из утверждения 4.2.3 могла по левому сыну вершины x узнать саму вершину x. Мы будем усложнять данный группоид, в первую очередь операцию на нем, таким образом, чтобы это было невозможно.

Заметим, что рассмотренная программа решает задачу принадлежности в случае дерева произвольной высоты.

В дальнейшем мы будем исследовать, выражает ли недетерминированная программа, что заданный элемент b группоида A принадлежит подгруппоиду, порожденному заданным элементом a.

–  –  –

Первые два варианта будем называть правильным выполнением f, третий неправильным.

Группоид характеризуется парой чисел (M, N ), где M число элементов квазигруппы, N число элементов полного бинарного дерева T. Всего в группоиде M N элементов. Отличительной особенностью этого построения является возможность неограниченного увеличения чисел M и N.

4.4 Квазигруппа сложного группоидного дерева Основы теории квазигрупп читатель может найти в [19], [16].

В группоиде A, каждый элемент является парой (q, t), где q Ql. Ql квазигруппа, l число элементов квазигруппы. l является степенью 4, l 1. Определим Ql по индукции.

Квазигруппа Q4 имеет 4 элемента. Операция на ней определена так:

Квазигруппа Q4i+1 это декартово произведение двух квазигрупп: Q4i и Q4. По построению l неограничено.

Введем понятие правого и левого деления в квазигруппе.

Утверждение 4.4.1. (Свойства квазигруппы) В каждой квазигрппе Ql, операция не коммутативна, не ассоциативна, идемпотентна. Для любых двух элементов a и b из Ql существуют результаты правого и левого деления Доказательство. 1 2 = 3, а 2 1 = 4, следовательно в Q4 операция не коммутативна. При декартовом произведении некоммутативных квазигрупп мы получим некоммутативную квазигруппу.

(1 2) 3 = 3, а 1 (2 3) = 1, следовательно в Q4 операция не ассоциативна.

При декартовом произведении неассоциативных квазигрупп мы получим неассоциативную квазигруппу.

Для Q4 идемпотентность видна из таблицы i-ый элемент главной диагонали это i. Декартово произведение не нарушает идемпотентности.

Индукцией по l числу элементов квазигруппы покажем, что существует деление слева и справа. Для Q4 элементы результаты делений существуют, так как в каждой строке и в каждом столбце есть все элементы Q4. Элемент, являющийся результатом деления (правого или левого) двух элементов квазигруппы Q4i b = (b1, b2 ) и a = (a1, a2 ) это элемент c = (c1, c2 ), где c1 определяются по индукции, а c2 определяется также как в базисе.

–  –  –

В диссертации рассматриваются три различных вида недетерминированных программ, каждому из которых соответствует свой сложностной класс. Сложностному классу Z+ соответствуют недетерминированные программы из класса P R+ с оператором инкремента. Факт о регистровой сложности термов, сформулированный ниже, относится к недетерминированным программ без оператора инкремента. Наконец, утверждения из главы 5 сформулированы для недетерминированных программ из класса P R. Это программы без оператора инкремента, но с оператором недетерминированного выбора, они будут подробно рассмотрены далее.

Факт о регистровой сложности термов накладывает общие ограничения на недетерминированные программы из класса P R0.

Определение 5.1.1. Недетерминированная программа принадлежит к классу P R0, если она принадлежит к классу P R+, и в ней нет оператора инкремента.

Определение 5.1.2. Класса языков Z0 это все языки, распознаваемые недетерминированными программами из класса P R0.

Факт 1. Если в недетерминированной программе нет операторов инкремента, и данная программа работает на вышеописанном группоиде A, то значение любой переменной в программе в дереве T находится на высоте меньшей или равной n, где n количество переменных в программе.

Доказательство. Формальное доказательство приведено в [10].

В общих чертах рассуждение следующее: для того чтобы вычислить значение любого элемента группоида лежащего на листе нам нужно не менее одной переменной. Однако, учитывая что случайных присваиваний на пути вычислений нет, для того чтобы вычислить значение элемента группоида лежащего на i уроне дерева снизу, нам нужно вычислить значение левого поддерева, сохранить вычисленное значение в некоторую переменную, и вычислить значение правого поддерева. То есть количество переменных необходимых для вычисления этого элемента не менее i. Разумеется это рассуждение верно при условии независимости вычислений.

Таким образом для вычисления значения элемента корня нам нужно количество переменных не меньшее высоты дерева.

Программы из класса P R0 подробно рассмотрены в [10].

Утверждение 5.1.1. Если в программе добавлены операторы деления справа и слева, то значение любой переменной в программе в дереве T находится на высоте меньшей или равной n, где n количество переменных в программе.

Доказательство. От противного пусть некоторая переменная в программе находится на высоте k, k n. Доказательство проведем индукцией по сложности терма, вычисляющего значение искомой переменной.

Базис:

В одной переменной нельзя вычислить вершину лежащую в дереве на высоте большей 1. Это следует из факта 1.

Шаг индукции:

Если последний оператор оператор деления, то ранее в программе вычислялся более простой терм, значение которого лежит выше в дереве.

f, то мы ранее вычислили значение одного из подЕсли последний оператор термов, сохранили в некоторую переменную, и вычислили результат второго подтерма. Значение второго подтерма находится в дереве на высоте k 1 и вычислялось в n 1 переменной. Этот подтерм проще исходного.

В обоих случаях мы свели доказательство к индукционному предположению, что и требовалось.

5.2 Программы с оператором недетерминированного выбо- ра

В этой части диссертации мы изменим класс недетерминированных программ, предположительно на более узкий. Новый класс недетерминированных программ мы будем обозначать через P R. Этот класс был введен И.В. Поповым в [18].

Все основные определения остаются в силе. Мы введем оператор недетерминированного выбора вместо оператора инкремента. Этот оператор осуществляет присваивание переменной x некоторого элемента носителя |A|. Семантика оператора такова: для присваивания выбирается такой элемент носителя, чтобы все тесты на пути вычислений были выполнены(если такой элемент существует).

Дадим более формальное определение:

Это изменение связано с тем, что наличие оператора инкремента в программе дает возможность использовать арифметику, что сильно затрудняет изучение этих программ.

Как и ранее, входом недетерминированной программы из класса P R является универсальная алгебра. Сигнатура универсальных алгебр, которые могут быть входом недетерминированной программы из класса P R, имеет вид k k k n R = c1, c2,..., cn1, f1 1, f2 2,..., fn2 2, где c1, c2,..., cn1 константы, каждая из k функций fj j kj -арная операция на A. В отличии от универсальных алгебр, на которых работали программы из класса P R+, в сигнатуре нет унарной операции. Сигнатура каждой недетерминированной программы из класса P R, R, включает в себя R, а также конечное множество X набор используемых в недетерминированной программе переменных. R = R, X.

5.3 Синтаксис класса недетерминированных программ P R Недетерминированные программы класса P R сигнатуры R задаются по индукции.

<

–  –  –

Количество переменных в программе конечно, фиксировано, и равно мощности множества X.

Определение 5.3.1. Класс программ P R содержит все вышеописанные программы всех допустимых сигнатур R.

В данных программах оператор инкремента заменен на оператгор x = rand;.

Семантика данного оператора следующая: если хотя бы при одном значении x из области определения |A|, можно добиться выполнения всех тестов, то присваивается произвольное такое значение.

Как и ранее, состояние пути вычислений это отображение множества переменных в предметную область.

Определим работу оператора недетерминированного выбора на состоянии пути вычислений s.

• x = rand. В этом случае s(x, t + 1) некоторый элемент предметной области;

s(y, t + 1) = s(y, t) для любого y не совпадающего с x.

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

Мы будем говорить, что путь вычислений вычисляет c в переменной x (c некоторый элемент универсальной алгебры), если при любых (допустимых, т.е.

таких, что все тесты истинны) способах проведения случайных присваиваний на этом пути вычислений, в результирующем состоянии s(T, x) = c.

Здесь и далее, если не оговорено иное, считаем, что программа начинает работать на s0 начальном состоянии, отображающим все переменные в 0.

Докажем, что ”почти” любая недетерминированная программа из класса P R может быть написана без использования параллельной композиции программ.

Определение 5.3.2. Две программы эквивалентны, если они распознают один и тот же язык.

Утверждение 5.3.1. Для каждой недетерминированной программы из класса P R, работающей на универсальной алгебре A, в которой есть две не равные константы a и b, существует эквивалентная ей, в которой не используется оператор объединения.

Доказательство. Действительно, рассмотрим произвольную программу из класса P R. Заменим в ней каждую конструкцию вида P1 = S1 S2 на P2 x = rand;

if (x == a) S1 endif

–  –  –

x в данном построении новая переменная, не использующаяся ни в каком другом месте программы P2 Докажем, что полученные программы эквивалентны. Пусть исходная конструкция P1 принимала вход w. Это верно тогда и только тогда, когда либо на S1, либо на S2, существует путь вычислений, на котором все тесты истинны. Но тогда существует вариант выполнения случайного присваивания из P2 (a или b соответственно), такой что в P2 существует путь вычислений, на котором все тесты истинны.

Пусть теперь P1 не принимала вход w. Тогда и в S1, и в S2, в любом пути вычислений есть ложный тест. Тогда и в P2 при любом способе проведения случайных присваиваний будет ложный тест. Если переменной x будет присвоено значение a, то в P2 в любом пути вычислений есть ложный тест из-за S1. Если переменной x будет присвоено значение b, то в P2 в любом пути вычислений есть ложный тест из-за S2. Иначе, в P2 есть ложный тест a == b?, который ложен по условию теоремы.

5.4 Определение терма

Определим понятие терма, соответствующего значению переменной x в момент времени t и соответствующее дерево вычислений. Ранее мы определяли состояние пути вычислений. Напомним, состояние пути вычислений функция, которая по переменной и моменту выполнения определяет элемент группоида. Однако в программе, в которой есть операторы недетерминированного выбора, нам часто не важен элемент группоида, но важны зависимости от констант и случайных присваиваний.

Зафиксируем некоторый путь вычислений u. Пронумеруем все случайные присваивания на u. Обозначим их как r1... rn. Напомним, что случайное присваивание это результат работы оператора недетерминированного выбора.

Определим терм индукцией по длине пути вычислений u.

Определение 5.4.1. Терм, соответствующий каждой переменной для пустого пути вычислений равен 0.

Осуществим переход от момента времени t 1 к моменту времени t. Другими словами, пусть термы для всех переменных, и всех путей вычислений длины t 1 построены. Рассмотрим оператор, выполняемый в момент времени t.

• x = f (y, z). Если переменной y в момент времени t 1 соответствовал терм u1 (a, l1...li ), переменной z в момент времени t 1 соответствовал терм u2 (a, v1...vj ), то переменной x в момент времени t соответствовует терм f (u1 (a, l1...li ), u2 (a, v1...vj )). l1...li, v1...vj случайные присваивания из r1... rn.

• x = rand. Пусть результат работы этого оператора недетерминированного выбора (случайное присваивание) пронумеровано как rj. Тогда переменной x в момент времени t соответствовует терм rj.

• x = y. если переменной y в момент времени t 1 соответствовал терм u1 (a, l1...li ), то переменной x в момент времени t соответствует терм u1 (a, l1...li ).

• x = a. В этом случае переменной x в момент времени t соответствовует терм a.

Термы, соответствующие остальным переменным не меняются.

Определение 5.4.2. Тест x == y? нетривиальный, если переменные x и y различны.

Определение 5.4.3. Случайное присваивание rj зависит от случайного присваивания ri, если существует нетривиальный тест, в котором участвуют rj и ri.

Случайное присваивание rj зависит от a, если существует нетривиальный тест, в котором участвуют rj и a.

Определение 5.4.4. Случайное присваивание rj явно зависит от a, если

• существует тест, в котором участвуют только rj и a.

• существует тест, в котором участвуют только rj, a и случайные присваивания Ri, явно зависящие от a.

Переменная x в момент времени t явно зависит от a, если в терме, соответствующем ее значению, участвуют только a и случайные присваивания явно зависящие от a.

Определение 5.4.5. Случайное присваивание rj является свободным, если не существует случайного присваивания ri такого, что rj явно зависит от ri.

5.5 О нормализации термов Напомним, что в рассматриваемом группоидном дереве A вводилось понятие ”правильного” и ”неправильного” выполнения f. ”Правильное” выполнение f приводило к движению по листьям, или к движению вверх по дереву (от сыновей к родителю). ”Неправильное” выполнение f не давало новых элементов группоида.

Определение 5.5.1. Переменная в терме называется свободной, если соответствующее ей случайное присваивание является свободным.

Определение 5.5.2. Терм находится в нормализованном виде, если каждое вхождение функционального символа f выполняется правильно, и каждая свободная переменная входит в терм ровно один раз.

Определение 5.5.3. Два терма эквивалентны, если их свободные переменные совпадают, и при любых значениях свободных переменных значения термов также совпадают.

Утверждение 5.5.1. Каждый терм эквивалентен нормализованному терму.

Доказательство. Проведем доказательство индукцией по сложности терма. Если терм является константой или случайным присваиванием то он уже находится в нормализованном виде.

Шаг пусть есть термы t1 и t2, t3 = f (t1, t2). t1 и t2 находятся в нормализованном виде. так как мы имеем конкретный путь вычислений со случайными присваиваниями, эквивалентными некоторым заранее заданным, то мы знаем, для каждой переменной, в каждый момент времени, второй элемент пары (q, t). Рассмотрим два случая.

• Если t1 и t2 находятся на таких вершинах, что операция f по определению не выполняется правильно, то результатом будет t1, который по условию находится в нормализованной форме. Свободные переменные результата также совпадают со свободными переменными t1.

• Пусть операция f выполняется правильно. Терм не будет в нормализованном виде, если какая-то переменная из одной части будет также участвовать и в другой части, или если переменная в какой-либо части встречается дважды.

Последний вариант невозможен, так как каждая из частей по индукции нормализованна. первый вариант невозможен, так как из нормальности следует, что все операции корректны, а значит все переменные из t1 и t2 лежат на разных непересекающихся поддеревьях.

5.6 О детерминированном вычислении низких вершин Утверждение 5.6.1. Для любого терма от a, высоты не более n, можно написать программу без случайных присваиваний, вычисляющую этот терм в памяти равной высоте терма x.

Доказательство. индукция по сложности терма x.

Базис:

x = a правильно вычисляет терм a в одной переменной.

Шаг индукции:

Пусть x есть f (x1 (a), x2 (a)). Для x1 (a) и x2 (a) по индукции существуют программы P1 и P2, вычисляющие их в k переменных. Будем считать, что все программы вычисляют результат в переменной x. Итоговая программа P 1; z = x; P 2; x = f (z, x),где z новая переменная, не использующаяся в P 2, работает в k + 1 переменной, что и требовалось.

Утверждение 5.6.2. Для любой переменной x, для любого момента времени t, если переменная x в момент времени t явно зависит от a, то можно написать программу без случайных присваиваний, которая будет правильно вычислять значение переменной x в той же памяти.

Доказательство. Индуция по сложности терма соответствующему значению переменной x в момент времени t:

Базис:

Если значение переменной является константой a, то искомая программа x = a.

Если значение переменной является случайным присваиванием r, явно зависящим от a, то будем доказывать индукцией по степени случайного присваивания, что можно написать программу, не использующую это случайное присваивание, но вычисляющую то же значение в той же памяти.

Базис индукции по степени случайного присваивания:

Для случайного присваивания первой степени существует тест вида ?v(a) = u(a, r) или ?u(a, r) = v(a), в котором участвует случайное присваивание r.

Индукция по сложности терма u.

Базис:

Если u(a, r) это r, то тест вида ?v(a) = u(a, r) можно заменить на присваивание r = v(a), при этом в программе никакие значения не изменятся.

Шаг индукции по сложности терма u:

u(a, r) = f (w(a), u1 (a, r)) Для более сложных термов или u(a, r) = f (u1 (a, r), w(a)), в силу того что в квазигруппе любое уравнение разрешимо, r являеся термом от a. Так как v(a) находится в дереве T выше чем r то по утверждению 3.3.1, этот терм может быть вычислен в меньшей памяти чем v(a).

Базис индукции по степени случайного присваивания доказан.

Шаг индукции по степени случайного присваивания:

Для случайного присваивания существует тест вида ?v(a, s1,..., sn ) = u(a, r, s1,..., sn ) или ?u(a, r, s1,..., sn ) = v(a, s1,..., sn ), в котором участвует случайное присваивание r и случайные присваивания s1,..., sn, которые имеют меньшую степень.

Снова будем рассуждать индукцией по сложности терма u.

Базис:

Если u(a, r, s1,..., sn ) это r, то тест вида ?v(a, s1,..., sn ) = u(a, r, s1,..., sn ) можно заменить на присваивание r = v(a, s1,..., sn ), при этом так как случайные присваивания s1,..., sn, имеют меньшую степень, по индукции их значения можно вычислить, не используя случайных присваиваний, в той же памяти.

Шаг индукции по сложности терма u:

Для более сложных термов в силу того что в квазигруппе любое уравнение разрешимо, r являеся термом от a, s1,..., sn. Так как v(a, s1,..., sn ) находится в дереве T выше чем r, а для s1,..., sn утверждение доказано, то этот терм может быть вычислен в той же памяти.

Шаг индукции по степени случайного присваивания доказан.

Шаг индукции по сложности терма, соответствующему значению переменной x:

Пусть значение x получено применением операции f из значений переменных y и z. Так как y и z имеют меньшую сложность, то утверждение очевидно.

5.7 Об усеченном дереве вычислений

Определим понятие дерева вычислений, соответствующего значению переменной x в момент времени t. Это понятие очень тесно связано с понятием терма. Каждому терму взаимно однозначно соответствует дерево вычислений. Мы вводим это понятие исключительно для наглядности некоторых дальнейших утверждений.

Дерево вычислений:

Зафиксируем некоторый путь вычислений. Пронумеруем все случайные присваивания на данном пути вычислений. Обозначим их как r1... rn.

Определим дерево вычислений индукцией по количеству тактов программы.

Определение 5.7.1. Базис:

В начальный момент времени дерево вычислений для каждой переменной состоит из одного корня, который помечен a.

Индукционный шаг:

Мы осуществляем переход от момента времени t 1 к моменту времени t.

Рассмотрим оператор, выполняемый в момент времени t.

• x = f (y, z). Создаем новую вершину E, которую помечаем f, и которая будет корнем дерева вычислений для переменной x в момент времени t, левым сыном этой вершины E делаем корень дерева вычислений для переменной y в момент времени t 1, правым сыном этой вершины E делаем корень дерева вычислений для переменной z в момент времени t 1.

• x = rand. Дерево вычислений для переменной x в момент времени t состоит из одной вершины, помеченной rj.

• x = y. Дерево вычислений для переменной x в момент времени t в точности совпадает с деревом вычисления для переменной y в момент времени t1.

• x = a. Дерево вычислений для переменной x в момент времени t состоит из одной вершины, помеченной a.

В остальных случаях дерево вычислений не меняется, т.е. дерево вычислений в момент времени t совпадает с деревом вычислений в момент времени t 1.

Определение 5.7.2. Усеченное дерево вычислений: дерево вычислений, у которого ограничена максимальная глубина, а некоторые листья помечены термами.

Каждому усеченному дереву вычислений взаимно однозначно соответствует дерево вычислений.

Докажем важное утверждение, для которого и было введено усеченное дерево вычислений.

Утверждение 5.7.1. Как и ранее n количество переменных в программе.

Для любой переменной x, которая принимает значение на вершине дерева T, лежащей выше уровня 2n + 1, для любого момента времени t, усеченное дерево вычислений соответствующее x:

• имеет ветку глубины меньшей n;

• каждый лист усеченного дерева зависит хотя бы от одного случайного присваивания.

Доказательство. От противного. Допустим такой ветви нет, то есть любая ветвь дерева вычислений имеет высоту больше n. Рассмотрим усеченное дерево вычислений, в котором листья помечены значенями соответсвующих поддеревьев. Тогда усеченное дерево полное бинарное дерево, случайные присваивания используются только в термах на листьях, все условия необходимые для факта 1 (регистровая сложность термов) выполнены, следовательно нам просто не хватит переменных для вычисления такого выражения, а значит такой случай невозможен.

Второе утверждение также доказывается с использованием факта 1. От противного: пусть есть лист, не зависящий от случайных присваиваний. Тогда этот лист усеченного дерева получен только используя константу a. По факту о регистровой сложности термов получаем, что этот лист усеченного дерева лежит на высоте меньшей n. Используя то, что переменная x по условию находится в дереве на высоте большей n + 1, получаем противоречие.

Доказанное утверждение характеризует количество операторов недетерминированного выбора в программе. Для того, чтобы получить некоторое значение, которое лежит в дереве достаточно высоко, необходимо использовать операторы недетерминированного выбора. Более того, зависимость эта очень сильная. Главная сложность, которую осталось разрешить зависимости случайных присваиваний (полученных в результате операторов недетерминированного выбора) друг от друга. Действительно, мы доказали, что каждое значение любой из переменных зависит от случайных присваиваний, но при этом случайные присваивания могут зависеть друг от друга, то есть могут быть тесты, в которых участвуют различные случайные присваивания. Из-за таких тестов, случайные присваивания, полученные в результате операторов недетерминированного выбора, могут получать все меньше значений, при которых все тесты выполнены, и, возможно, в конце концов, не будет 2-х таких наборов элементов группоида, которые можно использовать в операторах недетерминированного выбора, таких, что все тесты выполнены.

Следующее утверждение является решением исходной задачи, однако при этом мы вводим достаточо существенные ограничения на текст программы.

Напомним, что последний оператор программы P тест ?z = b, причем других тестов в которых используется b нет.

Определение 5.7.3. Условие неполного тестирования выполнено для недетерминированной программы P, если на некотором пути вычислений программы P существует случайное присваивание r, такое, что переменная z из последнего оператора программы зависит от r, и нет тестов, в которых участвует терм, зависящий от r.

Утверждение 5.7.2. Если в недетерминированной программе P для пути вычислений y выполнено условие неполного тестирования, то, при решении задачи G, существует способ проведения случайных присваиваний на пути y такой, что все тесты, кроме последнего, выполнены.

Доказательство. Воспользуемся частым способом решения такого типа задач постараемся изменить способ проведения случайных присваиваний и доказать, что при этом все тесты останутся выполнены. Подробнее: мы знаем, что программа P выполнена для некоторых значений констант a и b. Следовательно, существует путь вычислений и способ проведения случайных присваиваний, такой что все тесты выполнены. Зафиксируем путь вычислений. Будем изменять значения, которые присваиваются в операторах недетерминированого выбора. Наша цель получить такой путь вычислений и способ проведения случайных присваиваний, что для того же группоида, но для других констант a и b, на этом пути вычислений (при способе проведения случайных присваиваний ) все тесты выполнены.

Нам необходимо построить новый способ проведения случайных присваиваний.

Всем случайным присваиваниям, кроме r, оставим те же значение. Случайное присваивание r получит новое значение, отличное от старого, но находящееся на той же вершине дерева. Более формально: пусть случайное присваивание r, при способе проведения, принимало значение (q, t). Тогда при способе проведения случайных присваиваний, случайное присваивание r примет значение (q, t), где q = q.

Доказательство искомого утверждения теперь напрямую следует из условия.

Гипотеза 1. Для всех программ, решающих вычислительную задачу G, для некоторого входа выполнено условие неполного тестирования.

Обозначим класс программ, в которых выполнено условие неполного тестирования через P Rb.

Теорема 3. Класс языков, соответствующий классу недетерминированных программ P Rb разделен с P.

Доказательство. Так как задача G принадлежит P, нам достаточно показать, что никакая недетерминированная программа из класса P Rb не решает задачу G. Доказательство от противного. Предположим, некоторая программа P решает задачу G. Рассмотрим конкретный вход недетерминированной программы w, принадлежащий G. По условию неполного тестирования существует путь вычислений y, и способ проведения случайных присваиваний на пути y такой, что все тесты, кроме последнего, выполнены. Но тогда для некоторого другого входа w, который отличается от w только константой b, на пути вычислений y все тесты выполнены. Заметим также, что если в w константа b принимала значение (q1, t1 ), то в w константа b принимает значение (q2, t1 ). Однако, по определению G, w не принадлежит G. Теорема доказана.

Утверждение 5.7.3. Рассмотрим недетерминированную программу из класса P R. Пусть при некоторой нумерации группоида A в полном бинарном дереве T, соответствующему этому группоиду A, существует вершина v, такая что никакая переменная недетерминированной программы ни в какой момент времени не принимала значение на этой вершине v. Тогда существует такая нумерация группоида A, что никакая переменная недетерминированной программы ни в какой момент времени не принимает значение на отце вершины v.

Доказательство. Обозначим отца вершины v через w. Докажем это утверждение от противного. Допустим некоторая переменная x, в некоторый момент времени l, приняла значение на вершине w. Переменной x, в некоторый момент времени l, соответствует некоторое значение. Рассмотрим, какой оператор, менявший значение переменной x выполнялся последним.

1. Если это был оператор присваивания вида w = x, то рассмотрим, каким образом получена переменная x. Учитывая, что терм, соответствующий переменной x более простой, количество таких присваиваний конечно. 2. Если это был оператор присваивания вида w = f (x, y), то, так как по условию никакая переменная, в том числе x или y, не принимала значение на вершине v, этот оператор присваивания вырожденный, а значит эквивалентен оператору присваивания вида w = x, рассмотреному выше. 3. Если это был оператор y + +, то следует рассмотреть нумерацию элементов группоида, по которой переменная y больше переменной x.

5.8 Об эквивалентной системе утверждений

Далее мы введем понятие эквивалентной системы утверждений для пути вычислений недетерминированной программы из класса P R. Неформально, система утверждений, соответствующая пути вычислений это все тесты недетерминированной программы. Под тестами мы сейчас понимаем равенство или неравенство двух термов, которые соответствуют переменным, которые сравниваются в тексте программы. Заметим, что поведение программы полностью определяется всеми тестами (программа выполнена тогда и только тогда, когда все тесты истинны).

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

Можно считать, что переменная в уравнении соответствует паре момент времени работы программы и переменная недетерминированной программы. Решение системы утверждений соответствует набору конкретных значений, которые приняли переменные недетерминированной программы, во время выполнения пути вычислений. Идея этого перехода впервые сформулирована И.В.Поповым в [18].

Похожая задача рассматривалась в [20].

Мы рассматриваем квазигруппу Q.

Напомним, что она обладает следующими свойствами:

–  –  –

Определение 5.8.1. Переменная системы переменная, принимающая значения в квазигруппе Q. Константа системы константа, принимающая значения в квазигруппе Q.

Определение 5.8.2. Выражение системы определяется по индукции.

Базис: Пусть есть некоторая переменная системы x, которой соответствует вершина h в полном бинарном дереве T, и которая принимает значение q в квазигруппе Q. Тогда x является выражением. Этому выражению соответствует та же вершина h в полном бинарном дереве T, что и переменной системы. Это выражение принимает значение q.

Аналогично, каждая константа системы является выражением. Шаг индукции:

Пусть u и v выражения. Выражение u принимает значение q1, и ему соответствует вершина h1. Выражение v принимает значение q2, и ему соответствует вершина h2. Существует вершина h3, такая что h1 и h2 сыновья h3. Тогда f (u, v) выражение, которому соответствует вершина h3, и которое принимает значение q1 q 2.

Определение 5.8.3. Утверждение бывает двух типов. Пусть u и v выражения, которым соответствуют вершины h1 и h2. Тогда

–  –  –

Определение 5.8.5. Решение системы утверждений такие значения переменных системы, и такое отображение переменных системы в узлы дерева T, что все утверждения системы истинны.

Утверждение 5.8.1. По данному пути вычислений l можно построить систему утверждений в квазигруппе Q, такую, что эта система имеет решение, тогда и только тогда, когда существует способ проведения случайных присваиваний такой, что все тесты на пути вычислений l истинны.

–  –  –

Утверждение 5.8.2. Каждое решение системы утверждений 1 взаимно однозначно соответствует такому способу проведения случайных присваиваний, при котором на рассматриваемом пути вычислений все тесты истинны.

Доказательство. В прямую сторону. Пусть система утверждений 1 имеете решение r1,..., rn. Тогда каждое утверждение, при подстановке в него r1,..., rn выполнено. Рассмотрим способ проведения случайных присваиваний, соответствующий r1,..., rn. При этом способе оператор недетерминированного выбора ri выбирает ri.

Для каждого теста, значения термов, соответствующих переменным, сравнивающимся в этом тесте, совпадают. Это значит, что все тесты истинны.

Обратно:

Если на пути вычислений все тесты выполнены, то существует способ проведения случайных присваиваний r1,..., rn. Покажем, что r1,..., rn будет, в то же время и решением системы утверждений. Действительно, каждому уравнению соответствует некоторый тест. Тест выполнен, следовательно значения переменных, сравнивающихся в этом тесте совпадают. Следовательно, совпадают и значения термов, соответствующих этим переменным. Но это значит, что значения правой и левой частей уравнения совпадают, что и требуется.

Мы хотим разделить классы Z и P. Для этого, мы ввели в рассмотрение задачу определения принадлежности в группоиде особого вида. Пусть некоторая недетерминированная программа из класса P R решает проблему принадлежности в группоиде A. Тогда в этой программе будет путь вычислений, на котором все тесты выполнены, тогда и только тогда, когда значение константы b принадлежит подгруппоиду, порожденному значением константы a. Пусть константа b лежит в корне дерева T. Тогда в этой программе будет путь вычислений, на котором все тесты выполнены, тогда и только тогда, когда значение константы b в квазигруппе Q совпадает со значением константы a в квазигруппе Q. Рассмотрим этот конкретный путь вычислений на котором все тесты выполнены. Как мы доказали в 5.8.1, по этому пути вычислений, мы можем построить систему утверждений W, которая будет иметь решение.

По построению программы, в этой системе есть ровно одно утверждение, в котором участвет константа b. Пусть оно имеет вид u(a, r1,..., rn ) = b Отбросим его. Получим систему утверждений W.

Поставим задачу: отыскать решение системы утверждений W, такое, что u(a, r1,..., rn ) принимает значение, отличное от b. Допустим мы смогли это сделать. Тогда, мы нашли решение для системы утверждений W, которая является системой утверждений W, с другой константой b. Тогда в исходной программе существует путь вычислений, на котором все тесты истинны, константа b лежит в корне дерева T, и значение константы b в квазигруппе Q не совпадает со значением константы a в квазигруппе Q. Но это значит, что исходная программа не решает проблему принадлежности в группоиде.

Определение 5.8.6. Две системы утверждений эквивалентны, если каждое решение первой системы является решением второй и наоборот.

Определение 5.8.7. Будем говорить, что терм простой, если он состоит из константы или из случайного присваивания. Другими словами терм простой тогда и только тогда, когда в нем не используется знак функции f.

Определение 5.8.8. Будем говорить, что утверждение комплексное, если оно имеет вид f (t1, t2 ) = f (t1, t3 ) или f (t1, t2 ) = f (t3, t2 ) для равенств, или f (t1, t2 ) = f (t1, t3 ) или f (t1, t2 ) = f (t3, t2 ) для неравенств; где t1, t2, t3 термы.

Определение 5.8.9. Канонический вид системы утверждений

–  –  –

находится в каноническом виде, если

• Все термы, участвующие в системе утверждений, находятся в каноническом виде.

• В системе нет уравнения с простой правой или левой частью.

–  –  –

• В системе нет комплексных утверждений.

Утверждение 5.8.3. Каждая система уравнений эквивалентна системе уравнений в каноническом виде.

Утверждение 5.8.4. Если в системе есть уравнение, в котором есть ровно одно случайное присваивание, то существует программа, эквивалентная исходной, в которой нет этого случайного присваивания и этого теста.

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

• Если это случайное присваиванме входит в обе части уравнения, то, по определению нормализованного терма, данное уравнение тривиально.

• Если это случайное присваивание входит ровно в одну часть уранения, то вторая часть, по теореме о регистровой сложности термов, происходит в дереве достаточно низко, на уровне меньшем n. А это значит, что случайное присваивание можно заменить на детерминированный оператор присваивания конкретного терма от константы a.

Утверждение 5.8.5. Для любой системы уравнений найдется эквивалентная, находящаяся в каноническом виде.

Доказательство. Если в системе есть уравнение, в котором есть ровно одно случайное присваивание, то по утверждению 3.2.3 существует программа, эквивалентная исходной, в которой нет этого теста. По новой программе построим систему уравнений. Она эквивалентна исходной.

Пусть в системе есть уравнение с простой левой частью. Случай с правой частью полностью аналогичен.

Если левая часть случайное присваивание, то этот тест можно заменить детерминированным оператором присваивания.

константа a, то правая часть также простая, а значит Если левая часть

• либо это тривиальный тест вида ?t(a, r1,..., rn ) = t(a, r1,..., rn ), который можно ислючить из системы, при этом полученная система будет эквивалентна исходной.

–  –  –

Пусть в системе есть два уравнения, в которых есть совпадающие термы.

Для определенности будем считать, что уравнения имеют вид t1 (a, r1,..., rn ) = t2 (a, r1,..., rn ) и t1 (a, r1,..., rn ) = t3 (a, r1,..., rn ). Уравнения, как и тесты коммутативны, поэтому не имеет значения, правые их части или левые совпадают. Добавим уравнение t2 (a, r1,..., rn ) = t3 (a, r1,..., rn ). Полученная система эквивалентна исходной.

Если в системе есть комплексное уравнение вида f (t1, t2 ) = f (t1, t3 ) (второй вид рассматривается полностью аналогично), то исключим это уравнение, и добавим уравнение t2 = t3. Полученная система эквивалентна исходной.

Гипотеза 2. Если в канонической системе уравнений m переменных, то в ней не более m 1 уравнения.

Утверждение 5.8.6. Если в канонической системе уравнений m переменных, и все случайные присваивания проходят на листьях дерева, то в ней не более m1 уравнения.

Доказательство. Заметим, что переменные системы уравнений соответствуют конкретному случайному присваиванию, произошедшему в некоторый момент времени в недетерминированной программе, а не переменным недетерминированной программы. Индукция по k высоте дерева.

Базис У нас два листа, обозначим количество переменных на i-ом листе дерева за xi.

xi. Докажем, что количество возможных тестов minxi 1.

Всего переменных Все тесты происходят только в корне дерева. Рассмотрим случай, когда xj наименьший. Если xj = 1, то ни одного теста не возможно по условию канонической системы уравнений о сокращении. При xj = 2 возможен ровно один тест. Каждая следующая переменная системы уравнений дает возможность добавить не более одного теста, что и доказывает утверждение.

Гипотеза 3.

Если система уравнений в каноническом виде имеет решение (r1,..., rn ), то она имеет еще одно решение, обладающее следующим свойством:

Можно взять произвольную переменную системы ri, принимавшую значение ri = (q, t) и придать ей значение (q, t), для произвольного q. (Но на той же вершине дерева). При этом существуют такие значения остальных переменных системы, что все тесты выполнены.

6 Заключение В диссертации введена модифицированная модель вычислений, основанная на понятии недетерминированной программы. Определен класс языков, распознаваемых такими программами, и доказано, что он совпадает с классом NL. Тем самым первая из поставленных задач получила окончательное решение.

Построены примеры ограниченных классов недетерминированных программ, для которых соответствующие классы языков отделены от класса P.

Список литературы [1] Cook S.A. Variations on push–down machines, In Proc. 1st ACM Symp. on Theory of computing, pages 229–232, 1969.

[2] Cook S.A. Characterizations of push–down machines in terms of time–bounded computers, Journal of the ACM, 18(1):4–18, 1971.

[3] Cook S.A. Senti R. Storage requirements for deterministic polynomial time recognizable languages, Journal of Computer and System Sciences, 13(1):25– 37,1976.

[4] Cobham A. The intrinsic computational diculty of functions, Y. Bar-Hillel ed., Proc. of the 1964 International Congress for Logic, Methodology, and the Philosophy of Science, North Holland, Amsterdam, pp. 24-30, 1964.

[5] Immerman N. Nondeterministic space is closed under complementation, SIAM Journal on Computing 17, pp. 935-–938, 1988.

[6] Savitch W.J. Relationships between nondeterministic and deterministic tape complexities, Journal of Computer and System Sciences 4 (2), pp. 177 192, 1970.

[7] Arora S., Barak B. Computational complexity. A modern approach, Cambridge University Press. ISBN 978-0-521-42426-4, 2009.

[8] Papadimitriou C. Computational Complexity, Boston: Addison-Wesley. ISBN 0A.P. Stolboushkin and M.A. Taitslin Dynamic logics, In V.A. Mel’nikov, editor, Cybernetics and Computer Technology, volume 2, Nauka, Moscow, USSR, pp. 180– 230, 1986.

[10] Тайцлин М.А., Мусикаев И.Х. О динамических теориях свободных алгебр, Математический сборник, 180(3), стр. 307–321, 1989.

[11] Тайцлин М.А. Пример полиномиального запроса не распознаваемого в недетерминированной логарифмической памяти, Вестник Тверского государственного университета, серия прикладная математика 6(12), стр. 5–22, 2005.

[12] S.M.Dudakov, A.P. Stolboushkin and M.A. Taitslin Finite model theory, unpublished, Tver, 2006.

[13] Nisan N. Pseudorandom generators for space-bounded computation, Combinatorica Volume 12, Issue 4, pp. 449-461, 1992.

[14] Babai L., Nisan N. Multiparty protocols and logspace-hard pseudorandom sequences, Proceedings of the twenty-rst annual ACM symposium on Theory of computing, Seattle, Washington, USA. ISBN 0-89791-307-8, pp. 1–11, 1989.

[15] Wehler W. Universal algebra for computer scientists, Springer-Verlag Berlin And Heidelberg Gmbh et Co. ISBN 978-3-540-54280-3, 1992.

[16] Курош А. Г. Лекции по общей алгебре 2-е изд, М.: Физматлит, 1973.

[17] Носов Д.А. О синтаксическом определении класса языков, распознаваемых недетерминированными машинами Тьюринга на логарифмической памяти, Труды Института системного программирования РАН, том 26, Выпуск 2., стр.

275–296, 2014.

[18] Попов И.В. О невозможности задания линейного порядка при помощи недетерминированных программ специального вида, Вестник Тверского государственного университета, серия прикладная математика No3(10), стр. 25–36, 2008.

[19] Белоусов В. Д. Основы теории квазигрупп и луп, М.: Наука, 1967.

[20] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи, М.: Мир, 1982.



Похожие работы:

«Том 7, №5 (сентябрь октябрь 2015) Интернет-журнал "НАУКОВЕДЕНИЕ" publishing@naukovedenie.ru http://naukovedenie.ru Интернет-журнал "Науковедение" ISSN 2223-5167 http://naukovedenie.ru/ Том 7, №5 (2015) http://naukovedenie.ru/index.php?p=vol7...»

«Федеральное агентство по образованию Московский инженерно-физический институт (государственный университет) В.А. Кашурников А.В. Красавин Вычислительные методы в квантовой физике Рекомендовано УМО "Ядерные физика и технологии" в качестве учебного пособия для студентов высших учебн...»

«96 вычислительные методы и программирование. 2013. Т. 14 УДК 004.45 МОДЕЛИ И МЕТОДЫ ПРОФИЛИРОВАНИЯ И ОЦЕНКИ ВРЕМЕНИ ВЫПОЛНЕНИЯ ПОТОКОВ РАБОТ В СУПЕРКОМПЬЮТЕРНЫХ СИСТЕМАХ Г. И. Радченко1, Л. Б. Соколинский1, А. В. Шамакина1 Решение сложных инженерно-научных задач на распределенных...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Томский государственный университет систем уп...»

«RHYTHMODYNAMICS of NATURE 1 Международная Академия Информатизации Российская Академия Естественных Наук (РАЕН) Институт Ритмодинамики (МИРИТ) Ю.Н.Иванов РИТМОДИНАМИКА БЕЗАМПЛИТУДНЫХ ПОЛЕЙ *** ФАЗОЧАСТОТНАЯ ПРИЧИНА ГРАВ...»

«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ КАФЕДРА КОМПЬЮТЕРНЫХ ТЕХНОЛОГИЙ И СИСТЕМ Любич Леонард Яковлевич Выпускная квалификационная работа бакалавра Автоматическое управление посадкой квадрокоптера на движущееся основание Направление 010400 Пр...»

«СОГЛАСОВАНО ГУП ВНИИМС тель ГЦИ СИ В.Н. Яншин ^ 2006 г. Комплексы измерительно­ Внесены в Г осударственный реестр вычислительные и управляющие средств измерений противоаварийной защиты и Регистрационный № 6 Ш Л и Uh технологической безопасности Взамен № ProSafe-RS Выпускаются по технической документации фирм Yokoga...»

«Завьялова Зинаида Сергеевна САМОПРЕЗЕНТАЦИЯ ЛИЧНОСТИ В ЧАТ-КОММУНИКАЦИИ 09.00.11 – Социальная философия АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата философских наук Томск 2011 Работа выполнена на кафедре гуманитарных проблем информатики Федерального бюджетного государственного образовательного учреждения высшего профессиональног...»

«Министерство образования Республики Беларусь Учреждение образования БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ ПРОГРАММА вступительного экзамена в магистратуру по специальности 1-31 80 07 "Радиофизика" I Минск 2012 Программа составлена на основании типовых учебных программ дисциплин "Электромагнитные поля...»

«ПРАВИЛА регистрации договоров о передаче права на изобретение, полезную модель, промышленный образец, селекционное достижение, товарный знак, знак обслуживания и лицензионных договоров на их использование, договоров о полной или частичной передаче права на топологию интегральной микросхемы, полной или частичной...»

«ВВЕДЕНИЕ Рабочая программа по дисциплине "Маркетинг" предназначена для преподавателей, участвующих в образовательном процессе подготовки специалистов по специальности 080801 "Прикладная информ...»

«УДК 378.1 ВОЗМОЖНОСТИ ПРИМЕНЕНИЯ КОМПЬЮТЕРНОГО МОДЕЛИРОВАНИЯ В ПРОЦЕССЕ САМОАКТУАЛИЗАЦИИ ПРЕПОДАВАТЕЛЯ ИНФОРМАТИКИ В СОВРЕМЕННОМ ОБРАЗОВАТЕЛЬНОМ ПРОСТРАНСТВЕ © 2016 Е. И. Травкин канд. пед. наук, доцент кафедры компьют...»

«Санкт-Петербургский Государственный Университет Т.М. Петрова, Н.А. Позднякова, Ю.В. Соколова Методическое руководство для практических занятий по дисциплине "Аэрокосмические методы исследований" (для студентов 3-его курса) Кафедра картографии и геоинформатики 2016 год Оглавление Введение Съёмочные системы спутников Lan...»

«1 МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ГЕОДЕЗИИ И КАРТОГРАФИИ (МИИГАиК) КАФЕДРА ВЫСШЕЙ ГЕОДЕЗИИ Шануров Геннадий Анатольевич СПУТНИКОВАЯ ГЕОДЕЗИЯ Учебное пособие для студентов обучающихся по направлениям: "геодезия и...»

«Министерство образования Республики Беларусь Учреждение образования БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ УТВЕРЖДАЮ Проректор по учебной и воспитательной работе _ С.К. Дик 25 апреля 2016г. ПРОГРАММА вступительного экзамена в магистратуру по специальности 1-31 80 10 Теоретические основы информатики...»

«Министерство образования Республики Беларусь Учреждение образования "Белорусский государственный университет информатики и радиоэлектроники" ПРОГРАММА ВСТУПИТЕЛЬНОГО ЭКЗАМЕНА для магистерской подготовки по специальности 1-40 80 01 Элементы и устрой...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Государственное образовательное учреждение высшего профессионального образования "Новосибирский государственный университет" (НГУ) Факуль...»

«Программа дисциплины "Информатика с основами геоинформатики" Авторы: проф. И.К. Лурье, доц. И.В. Зотов, с.н.с. Лукьяница А.А. Цели освоения дисциплины – получение общих и специальных знаний в области информатики и геоин...»

«368 вычислительные методы и программирование. 2011. Т. 12 УДК 519.6; 533.72 ДЕТЕРМИНИРОВАННЫЙ МЕТОД ЧАСТИЦ-В-ЯЧЕЙКАХ ДЛЯ РЕШЕНИЯ ЗАДАЧ ДИНАМИКИ РАЗРЕЖЕННОГО ГАЗА. ЧАСТЬ I Е. А. Малков1, М. С. Иванов1 Предлагается метод численного решения уравнения Больцмана, п...»

«4/2012(11) издается с декабря 2010 г. ISBN 978-5-91137-222-4 Кольского научного центра РАН Главный редактор – академик В.Т. Калинников Редакционный совет: академик Г.Г. Матишов, академик Н.Н. Мельников, Заместители главного редактора академик Ф.П. Митрофанов, д.г.-м-н. В.П. Петров чл.-корр. В.К. Жиров,...»

«279 вычислительные методы и программирование. 2013. Т. 14 УДК 519.6 TTDock: МЕТОД ДОКИНГА НА ОСНОВЕ ТЕНЗОРНЫХ ПОЕЗДОВ Д. A. Желтков1, И. В. Офркин2, E. В. Каткова2, А. В. Сулимов2, е В. Б. Сулимов3, Е. Е. Тыртышников4 Разработан метод докинга на основе тензорных поездов, позволяющий с высокой вероятностью найти положение, в ко...»

«413 вычислительные методы и программирование. 2012. Т. 13 УДК 536.75, 538.9 ПРОГРАММА MEL АТОМИСТИЧЕСКОГО МОДЕЛИРОВАНИЯ ФУНКЦИОНАЛЬНЫХ СЛОЕВ СОЛНЕЧНЫХ ЭЛЕМЕНТОВ Ф. В. Григорьев1, А. Н. Романов1, И. В. Офркин2, А. В. Сулимов2, В. Б. Сулимов1,2 e Предложен...»

«Программа курса "Компьютерная графика". 1. Организационно-методический раздел 1.1 Название курса Компьютерная графика Направление – 552800 Информатика и вычислительная техника. Раздел – общепрофессиональные дисциплины. Компонент – федеральный.1.2 Цели и задачи курса О...»

«Тематический раздел: Теоретическая и компьютерная химия. Полная исследовательская публикация Подраздел: Физическая органическая химия. Регистрационный код публикации: 11-27-14-1 Публикация доступна для об...»

«Материалы для студентов "Информатика и ИКТ" 1 курс Содержание занятия Информатика и ИКТ Лекция 4 Подходы к измерению информации. Единицы измерения информации. Хранение информационных объектов различных видов на различных цифровых носителях. Определение объемов различных носителей информации. Архив и...»

«СОДЕРЖАНИЕ 1 Перечень планируемых результатов обучения по дисциплине, соотнесенных с планируемыми результатами освоения основной образовательной программы 02.03.02 "Фундаментальная информатика и информаци...»

«1 УДК 004.415.52 Методы доказательства корректности программ с хорошей логикой В.И. Шелехов Институт Систем Информатики СО РАН, г. Новосибирск, e-mail: vshel@iis.nsk.su Логика программы – предикат, истинный на значениях переменных тогда и только...»








 
2017 www.doc.knigi-x.ru - «Бесплатная электронная библиотека - различные документы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.