Анализ сложности вычисления булевых функций ветвящимися программами с ограничениями тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Анализ сложности вычисления булевых функций ветвящимися программами с ограничениями

Специальность: 01.01.09 — дискретная математика и математическая кибернетика

Автореферат

диссертации на соискание ученой степени кандидата физико-математических паук

11 НОЯ 2015

Казань - 2015

005564245

005564245

Работа выполнена на кафедре теоретической кибернетики института вычислительной математики и информационных технологий ФГАОУ ВО "Казанский (Приволжский) федеральный университет".

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

Фарид Мансурович Аблаев

доктор физико-математических наук, профессор,

ФГАОУ ВО "Казанский (Приволжский) федеральный университет".

Официальные оппоненты: Валерий Борисович Алексеев

доктор физико-математических наук, профессор, заведующий кафедры математической кибернетики факультета вычислительной математики и кибернетики ФГБОУ ВО "Московский государственный университет имени М.В. Ломоносова", Светлана Михайловна Грабовская

кандидат физико-математических наук, старший преподаватель кафедры компьютерных технологий

ФГБОУ ВПО "Пензенский государственный университет".

Ведущая организация:

ФГБОУ ВПО "Казанский национальный исследовательский технический университет им. А.Н.Туполева-КАИ".

Защита диссертации состоится — 17 декабря 2015 года в 14:30 на заседании диссертационного совета — Д 212.081.24 при Казанском федерального университете по адресу: 420008, Казань, ул. Кремлевская, д.18., институт вычислительной математики и информационных технологий, аудитория 1011.

С диссертацией можно ознакомиться в научной библиотеке им. Н.И.Лобачевского Казанского федерального университета и на сайте kpfu.ru

Автореферат разослан_20 г.

Ученый секретарь диссертационного /

Совета Д 212.081.24 — при КФУ "" А.И.Еникеев

доцент

Общая характеристика работы

Актуальность темы исследования. Анализ и классификация алгоритмов с точки зрения вычислительной сложности является одним из основных аспектов для понимания внутренней природы задачи и алгоритма ее решения. Центральным аппаратом такого анализа алгоритмов являются нижние оценки сложности.

Важной известной проблемой является соотношение классов Р и NP. При этом остается много открытых вопросов о структуре класса Р. И, в частности, известных классов LSPACE и NG, входящих в класс Р. Во второй половине прошлого века были введены различные модели вычислений с разными вариантами ограничений, которые позволяли решать ряд вопросов для классификации сложности, к таким моделям относятся ветвящиеся программы. Для них было доказано, что LSPACE /poly = BP, где LSPACE /poly — это неоднородный класс сложности для машины Тю-ринга, использующей логарифмическую память и подсказку не более, чем полиномиального размера, a BP — класс булевых функций, вычислимых ветвящимися программами полиномиальной сложности. Кроме того, было доказано, что NC1 = BPconst, где класс NC1 — это класс булевых функций, вычислимых схемами из функциональных элементов логарифмической глубины (JVC1 С NC), a BPcangt — класс булевых функций, вычислимых ветвящимися программами полиномиальной сложности константной ширины.

Начиная с 90-х годов интенсивно исследовалась сложность реализации булевых функций, входящих в класс BPconst. Для целого ряда моделей ветвящихся программ были доказаны нижние оценки сложности реализации в них булевых функций, и на основе этих оценок построены иерархии сложности.

Большие усилия были направлены на исследования моделей ветвящихся программ с ограничением на количество считываний переменных. Для модели к раз читающих недетерминированных ветвящихся программ (&-NBP)

в 1993 году Бородиным и соавторами [3] были получены нижние оценки для явно заданной функции, показывающие необходимость экспоненциального размера программы для малых к. Авторы рассмотрели "синтаксическую" модель, для которой ограничение на количество считывания вводится для любого пути от начальной вершины до финальных, и "семантическую", для которой ограничения вводились только па вычислительных путях. Оценка была получена для "синтаксической" модели.

• Техника, использованная в [3], основывалась на представлении функции в виде булевой формулы специального вида. Таким образом процесс вычислений был описан функционально.

В недетерминированном случае рассматривалась более общая модель к-ВР, для которой были доказаны нижние оценки в работах Окольнишнико-вой [5]. В 1997 году она доказала нижнюю оценку сложности для недетерминированной /с-ВР для явно заданной булевой функции /кЫк/2+с^ показав, что эта функция требует экспоненциального размера для вычисления в к-ВР. На основе этой оценки была доказана иерархия классов булевых функций, вычислимых недетерминированными к-ВР полиномиального размера: МР-/сВР С КР-(ЫпА;/2 + С)ВР. Данная иерархия справедлива для к = о(\/1п п/ 1п1пп).

• Техника, использованная Окольнишниковой, схожа с техникой, которую использовали Бородин и соавторы в работе [3]. Она основывалась на представлении функции в виде булевой формулы специального вида и анализе этой формулы.

Оценку Окольнишниковой улучшил Татачар [6] в 1998 году, доказав нижнюю оценку для функции НБРЬ+К Он показал, что недетерминированная /с-ВР, вычисляющая эту функцию, должна иметь ширину не менее ехр{п}1к+12~2кк~А}, используя этот результат доказал иерархию классов сложности: ИР-(А; — 1)ВР С МР-/сВР. Таким образом, была доказана более

строгая иерархия по сравнению с результатами Околышшниковой. Данная иерархия справедлива для к = o(loglogn).

• Автор в своей работе использовал модификацию метода, основанного на коммуникационных протоколах.

Позже Айтаи [1] в 2005 году доказал нижнюю оценку для более общей модели: ветвящихся программ без ограничений, показав, что функция N+(XV) не может быть вычислена ветвящейся программой длины кп, для к = const и размера менее, чем 2п£, где е > 0.

• Автор в своей работе использовал как модификацию метода, основанного на коммуникационных протоколах, так и функциональный подход.

В вероятностном случае для /с-BP Хромкович и Заурхов [4] в 2003 году, доказали нижнюю оценку для функции т — Masked — PJk,n■ Таким образом, они показали, что вероятностная fc-BP с (0.5 — ^-изолированной точкой сечения, вычисляющая эту функцию, должна иметь размер не менее 2Q(Na/k3)^ где а _ 21одЗ). На основе полученного результата авторы

доказали иерархию классов сложности: BPP-(fc — 1)ВР С BPP-fcBP. Данная иерархия справедлива для к < logn/3.

• Авторы в своей работе использовали метод, аналогичный тому, который использовал Татачар в работе [6].

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

решений (Ordered Binary Decision Diagrams, сокращенно OBDD). Обобщением OBDD является к раз читающие OBDD (fc-OBDD). Модели /с-OBDD (к > 1) имеют широкое практическое применение в тестировании СБИС, а также при построении /г-проходных потоковых алгоритмов, используемых при обработке больших объемов данных, поэтому важным вопросом является построение иерархий классов сложности булевых функций, реализуемых в этих моделях по параметру к. Неформально можно сказать, что построение иерархий отвечает па вопрос: "сможет ли модель fc-OBDD решить задачу, если ей дать больше времени?".

Заметим, что fc-OBDD является "синтаксической".

Для /¿-OBDD Боллинг и соавторы [2] в 1998 доказали нижнюю оценку для булевой функции PJk (Pointer Jumping): для (к — l)-OBDD, вычисляющей функцию PJk, требуется размер не менее На основе этой оценки была доказана иерархия классов булевых функций, вычислимых к-OBDD полиномиального размера (или, что в данном случае тоже самое, полиномиальной ширины): Р-{к — l)OBDD С P-fcOBDD. Данная иерархия справедлива для к = о(п1/21од3/2п).

• Авторы в своей работе применили метод моделирования работы к-OBDD в коммуникационных протоколе«.

Исследования диссертационной работы посвящены уточнению иерархии классов сложности fc-OBDD.

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

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

Научная новизна. В диссертации рассмотрены две техники доказательства нижних оценок: "Коммуникационное моделирование /с-ОВОБ" и "Функциональное описание /с-ОВОБ". Эти две техники взаимно дополняют друг -друга. Получены следующие новые результаты:

1. "Коммуникационное моделирование к-ОВТ)]У' — это подход, использующий представление /с-ОВОО в виде специального коммуникационного вычислителя. Этот подход позволил уточнить оценки числа подфункций N(f ) для булевых функций /, реализуемых в /с-ОВББ.

• Это уточнение позволяет доказать новые оценки сложности вычисления булевых функций в детерминированной, недетерминированной и вероятностной /с-ОВБО (А;-ОВБО, й-ГГОВОБ, /г-РОВББ).

• На основе установленных нижних оценок для ЛГ(/) доказаны следующие уточнения иерархий для детерминированной, недетерминированной и вероятностной /с-ОВБО для константной, полилогарифмической и сублинейной ширины.

• На основе анализа числа N(f) для некоторых явно заданных функций / получены нижние оценки сложности детерминированной и недетерминированной ОВБО, вычисляющей /. Это позволило построить иерархии по ширине для классов булевых функций, вычислимых ОВББ и МОВББ, а также отношения между классами для разных моделей.

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

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

• Построены иерархии классов булевых функций, которые являются характеристическими для языков, вычислимых детерминированными и недетерминированными двухсторонними автоматами с переменной структурой. Иерархии базируются на доказанных нижних оценках.

Ограничение подхода "коммуникационного моделирования fc-OBDD" состоит в следующем: kw log w < п для детерминированного случая и kw2 < п для недетерминированного и вероятностного случаев, где w — ширина fc-OBDD. То есть, он подходит только для моделей менее, чем линейной ширины.

2. "Функциональное описание fc-OBDD" — это функциональный подход для анализа вычислительных процессов в fc-OBDD и fc-NOBDD. Этот подход, во-первых, позволяет моделировать процесс вычисления в fc-OBDD с помощью недетерминированной OBDD. Во-вторых, он позволяет описать функцию /, вычислимую fc-OBDD (недетерминированной fc-OBDD) в виде булевой формулы специального вида.

• На основе функционального представления процесса вычисления получена нижняя оценка для некоторых явно заданных функций /, вычислимых в детерминированной и недетерминированной fc-OBDD.

• На основе этого подхода доказаны уточнения иерархий для детерминированной и недетерминированной fc-OBDD полиномиальной, суперполиномиалыюй и субэкспоненциалыюй ширины.

Техника "Коммуникационного моделирования fc-OBDD" является обобщением идей, представленных в работах [2], [4], [6]. Техника "Функциональ-

ное описание fc-OBDD" является обобщением идей, представленных в работах [3], [5].

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

Апробация работы. Результаты диссертации были представлены на российских и международных конференциях и семинарах: X международном семинаре "Дискретная математика и ее приложения" (Москва, 2010 г.), XI международном семинаре "Дискретная математика и ее приложения", посвященный 80-летию со дня рождения академика О. Б. Лупанова (Москва, 2012 г.), на XVII международной конференции "Проблемы теоретической кибернетики". (Казань, 2014 г.), на конференции "6th Workshop on Non-Classical Models of Automata and Applications NCMA 2014" (Германия, Kac-сель, 2014 г.), на конференции "16th International Workshop on Descriptional Complexity of Formal Systems" (Финляндия, Турку 2014), на итоговых конференциях Казанского федерального университета и на семинарах по классическим и квантовым вычислениям Казанского федерального университета.

Публикации. По теме диссертации опубликовано 10 работ, в том числе 3 - в журналах, входящих в перечень ВАК.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы из 45 наименований, включая работы автора. Объем диссертации составляет 135 страниц машинописного

текста.

Основное содержание работы

Метод "коммуникационного моделирования /c-OBDD".

В главе 1 излагается метод "коммуникационного моделирования /c-OBDD". Это подход представления /г-OBDD в виде специального коммуникационного вычислителя. На основе этого подхода доказаны новые оценки сложности вычисления булевых функций в детерминированной, недетерминированной и вероятностной /c-OBDD (/c-OBDD, /с-NOBDD, /с-POBDD) в терминах количества подфункций N(f).

Приведем определение количества подфункций булевой функции. Рассмотрим булеву функцию / = f(X) и разбиение тт = (Ха, Хв) переменных X. Для каждого фиксированного набора а будем рассматривать отображение р : Ха —> ст. Подфункцию /\р над переменными из множества Хв получаем из функции /, фиксируя переменные из Ха в соответствии с отображением р. Обозначим за Nn(f) количество различных подфункций, получаемых при рассмотрении всех возможных а. Рассмотрим некоторую перестановку 9 = (ji,---,jn) чисел от 1 до п и множества Х(в, и) = {xju,„tXju} для некоторого и € {l,...,n—1}, тогда количеством подфункций функции / назовем величину N(f) = min0 maxue{ij...iIJ_1}

Теорема 1.4.1 Пусть булева функция f(X) представима в /с-OBDD ширины w. Тогда N(f) <

Теорема 1.4.7 Пусть булева функция f(X) представима в fc-NOBDD ширины w. Тогда N(f) < 2W(^W+1).

Теорема 1.4.10 Пусть булева функция f(X) представима в /c-POBDD

Теорема 1.4.1 была опубликована в работах 2 и 5 из списка публикаций, Теоремы 1.4.7 и 1.4.10 опубликованы в работе 7.

Ограничение метода. В связи с тем, что по определению количество подфункций функций N(f) не может превосходить количество различных входных наборов, то возникают очевидные ограничения метода: для детерминированной модели: ((к — l)w +1) log2 w < п, для недетерминированной модели: w((к — 1)го + 1) < га, для вероятностной модели: (к + l)w2(log2(log2 к + log2w)) = о{п).

Таким образом, полученный результат улучшает оценки, полученные в работе Болинга и соавторов в случае, если w < п1^2, и в работах Околышш-никовой, Татачара, Хромковича и Заурхофа, в случае w = o(ra/(logra)2), причем наилучшее продвижение получено, если w — константа.

Иерархии для fc-OBDD. На основе установленных нижних оценок доказаны следующие уточнения иерархий для детерминированной, недетерминированной и вероятностной /c-OBDD.

Пусть k—OBDDw — множество булевых функций, вычислимых fc-OBDD ширины w, a k—OBDDw = LLeiv к—OBDDw, где W — некоторое множество. Аналогично определим k—NOBDDw и к—POBDDw для к-NOBDD и fc-POBDD соответственно. В качестве W рассмотрим следующие множества: константы const = {w : w > 20, w = const}, к = o(n/log2n); полином над логарифмом W' = {(log2 п)\ : t\ = const}, polylog — множество линейных комбинаций над W; sublineara = [w : w > 20, w < С ■ na, для некоторой константы С}.

В работе доказаны следующие иерархии при указанных ограничениях, которые следуют из ограничений для нижних оценок:

Следствия 1.4.6, 1.4.9, 1.4.12 Справедливы следующие соотношения:

(k/log2 log2 n) - OBDDConst £ k—OBDDconst,

(k/log2log2n)-NOBDDCOnst £ k—NOBDDconst, (k/(log2nlog2log2n))-POBDDconst С k—POBDDconst,

где к = о(п/ п).

(к/п£) -ОВВВро1у1ой С к-ОВВВро1укж,

(к/п£) -ГЮВВВр01У10й С к-]МОВВВро1у1о2,

(к/п£)-Р0ВВВр01у108 С к-РОВВВро1У,ое,

где е > 0, к = о(п1-е), пе < к.

(к/(па(1о§2п)2))-ОВВВ5иЫтеаг„ £ к-ОВВВйиЬИпсаГа, где 0 < а < 0.5 - е, £ > 0, к > па(к^2 п)2, к = о(п1_а/ п),

(к/(п2а(^2п)2))-КОВВВ8иы!пеаГ<> £ к-КОВВВ5пЬПпеаг„, где 0 < а < 1/3 - е, £ > 0, к > п2а(1с^2 п)2, к = о{п1~а/ к^2 п).

(кДп^^П^^-РОВВВ^Ышеаг,, С к-РОВВВ8цЫтеага,

где 0 < а < 1/3 - е, £ > 0, к > п2а( 1с^2 п)3,к = о(п1_а/ log2 п).

Таким образом, для детерминированной модели, при ширине менее, чем п1/3, иерархия справедлива для к больших, чем в лучшей известной ранее иерархии Боллинг и соавторов [2], в частности наибольшее продвижение получаем при константной ширине.

Для недетерминированной модели полученный результат улучшил существующие результаты для более общей модели, полученный Околышшнико-вой [5] и Татачаром [6], уже при ширине менее чем тг0-49, также наибольшее продвижение получаем при константной ширине.

Для вероятностной модели полученный результат улучшил существующий результат для более общей модели [4] уже при ширине менее чем п0,32, также наибольшее продвижение получаем при константной ширине.

Данные результаты были опубликованы в работе 7 из списка публикаций по диссертации.

Иерархии для ОЕШБ и N0600. В главе 2 на основе анализа количества подфункций получены нижние оценки для некоторых явно заданных функций, вычислимых в детерминированной и недетерминированной ОВББ, которые позволили построить следующие иерархии по ширине для классов булевых функций, вычислимых ОВББ и ИОВОВ:

Теорема 2.2.1 Для любых целых п,<1 = (1(п), 16 < d < 2"/4, справедливы следующие соотношения: ОЕШО|а/8]_1 С ОВББС1 и ]МОВББ|а/8]_1 £

КОВБВа.

Кроме того, для сублинейной ширины (при 1 < <1 < п/2) иерархия уточнена:

Теорема 2.1.1 Для любых целых чисел п, й = с1(п) таких, что 1 < <1 < п/2, справедливы следующие соотношения: ОВББ,1-1 С ОВББа и КОВББ^ С N0600(1-

А также получены соотношения между детерминированной и недетерминированной моделями:

Теорема 2.2.4 Для любых целых чисел п, й = <1(п), и с1' = й'(п) таких, что (1 < 2"/4 и 0(1ой2(£/+ 1) 1о§2 к^2(с(+1)) < д! < с1/8 — 1, справедливо следующее: 1ЧОВББц082((1)] С ОВББа, ОВББа и ¡ЧОВББ^ не сравнимы.

Для сублинейной ширины:

Теорема 2.1.4 Для любых целых п, d = с1(п), и в! = с1'{п) таких, что (1 < п/2 и 0{\.o^d\og2\og2d) < d' < d — 1, справедливы следующие утверждения: ГЧОВББ^^ С ОВББа, ОВВБа и КОВББ^ не сравнимы.

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

Приведенные результаты были опубликованы в работах 1 и 6 из списка публикаций на тему диссертации.

Иерархия для А:-ОВОО по ширине. На основе нижних оценок для /г-ОВОБ доказаны следующие иерархии по ширине для детерминированной, неде-

терминированной и вероятностной моделей:

Теоремы 2.3.1, 2.3.2, 2.3.3 Для целых чисел к = к(п),ю = м(п), таких, что 2кт(2ги + |"1оц2 /с] + |~к^22«/|) < п, к > 2,ш > 20,0 < е < 0.5 — <5, <5 > 0, выполняются следующие собственные включения:

к - МОВВВ^1о&№)1/2/^ С к - Г«ЮВВВ№, где [(го 1оё2 ю)1/2/7\ > 1

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

Приведенные результаты были опубликованы в работах 3, 6, 7 и 10 из списка публикаций на тему диссертации.

Иерархии для двухсторонних автоматов с переменной структурой. В главе 3 подход представления в виде специального коммуникационного вычислителя применен к моделям детерминированных и недетерминированных двухсторонних автоматов с переменной структурой. На его основе доказаны нижние оценки для характеристических функций / языков, вычислимых такими автоматами.

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

Отличие от классического двухстороннего автомата состоит в том, что функция переходов зависит от номера обозреваемого символа, кроме того, количество состояний может зависеть от длины слова. Таким образом, мы строим для каждой длины слова п свой автомат Ап. Автомат распознает некоторый язык Ь = игде Ьц — все слова длины г из языка Ь, если есть последовательность автоматов Ах, Ач ..., такая, что Ai распознает язык

к - ОВВБ1№/16]_3 С к - ОВВВ„, где ю > 64

к-ОВВВ

1 У]Ъё21У 18 \оё2к ' .

■У >1

Определение двухстороннего неоднородного детерминированного автомата с переменной структурой, работающего на входном наборе X = (х\,..., хп) (2DA„) Dn отличается от определения классического двухстороннего автомата тем, что количество состояний может зависеть от п, функция перехода зависит не только от обозреваемого символа и состояния, но и от текущей позиции. Аналогично можно определить недетерминированную модель 2NA„.

Множество входных наборов X, которое принимает 2DA„(2NAn) Dn, образует язык Ln. С другой стороны, мы можем говорить о функции /п : {0,1}" —> {0,1} такой, что fn{X) = 1, тогда и только тогда, когда Dn принимает набор X. Тогда можно говорить, что автомат Dn вычисляет функцию fn. Отметим, что функция fn является характеристической функцией для языка Ln. В случае, когда мы говорим о булевых функциях, то изменение порядка переменных не изменяет саму функцию (что нельзя сказать о языке). В связи с этим рассмотрена обобщенная модель 2DAn и 2NA„, вычисляющая булеву функцию над п переменными: Двухсторонний неоднородный детерминированный 0-автомат с переменной структурой, работающий па входном наборе X = (xi,... ,хп), (2DA®) Den — это 2DAn, у которого перед выполнением переменные на входной ленте были размещены в порядке в, где в — некоторая перестановка чисел от 1 до п. Аналогично можно определить недетерминированную модель 2NA®. Для описанных видов автоматов рассматриваются классы булевых функций, вычислимых автоматами размера d(n): 2DSIZE(d(n)), 2NSIZE(d(n)), 2D©SIZE(d(n)), 2N0SIZE(d(n)).

Рассматриваемые виды автоматов промоделированы с помощью автоматных коммуникационных протоколов, благодаря чему получены нижние оценки для классов булевых функций, вычислимых рассматриваемыми автоматами:

Теорема 3.2.1 Пусть булева функция f(X) вычислима 2DA® размера d. Тогда N(f) < (d+l)ä+1.

Теорема 3.3.1 Пусть булева функция f(X) вычислима 2NA® размера d. Тогда N{f) < 2(d+1)2.

В детерминированном случае оценка применима, когда (d+1) log(d+l) < п, а в недетерминированном — когда (d+1)2 < п, ввиду того, что N(f ) < 2".

Были построены иерархии, базирующиеся на найденных нижних оценках:

Теоремы 3.2.3, 3.3.3 Пусть d = ci(n) — целое число, тогда справедливы следующие соотношения:

2D0SIZE ([(d — 4)/13j -4) С 2D0SIZE(d), где (d+1) log(d+l) < n,

2N0SIZE Q4/L(d-4)/13j -4J) С 2N©SIZE(d), где (d+ l)2 < n.

А также 2DSIZE ([(d - 4)/13j - 4) С 2DSIZE(d), и в недетерминированном случае справедливо следующее собственное включение:

2NSIZE — 4)/13j -4j) g 2NSIZE(d).

Кроме того, получен результат о том, что две модели 2DA® и 2DAn, а также 2NA® и 2NA„ не сравнимы:

Теоремы 3.2.4, 3.3.4 Классы 2DSIZE(d) и 2D0SIZE(d') не сравнимы при (Pin) <п/2-1, 4 < d'(n) < L(d - 4)/13j -4. Классы 2NSIZE(d) и 2N0SIZE(d') не сравнимы при следующих ограничениях: d2(n) <п/2 — 1 и 4 < d'in) < [л/К^ — 4)/13j -4].

Приведенные результаты были опубликованы в работе 9 из списка публикаций на тему диссертации.

Метод "функционального описания fc-OBDD".

Метод, использованный в первом разделе, оценивает число подфункций. Эта величина относительно легко считается, однако не выявляет всю структуру функции. В связи с этим разработан альтернативный метод (функциональный подход) представления функции, выявляющий структуру булевой формулы функции. Этот метод позволил доказать нижнюю оценку и получить уточнение иерархии для fc-OBDD для большей (в том числе полиномиальной) ширины.

В главе 4 предложен функциональный подход для анализа вычислитель-

пых процессов в /г-OBDD и fc-NOBDD. Подход позволяет моделировать процесс вычисления в fc-OBDD с помощью недетерминированной OBDD большего размера, а также позволяет описать функцию /, вычислимую fc-OBDD (недетерминированной fc-OBDD) Р ширины w в следующем виде:

Ш*-1 к

f(X)=\J /\ди(Х) i=1 j=1

где gij — функция, представимая в виде OBDD (недетерминированной OBDD) ширины w. Данный результат представлен в следующей теореме:

Теорема 4.2.1 Пусть f(X) — некоторая булева функция, которую распознает k — NOBDD Psj ширины w с порядком чтения в. Тогда / может быть вычислена с помощью некоторой NOBDD Р' ширины wlk~l с порядком чтения в.

На основе этого подхода доказаны следующие уточнения иерархий для детерминированной и недетерминированной A;-OBDD:

Следствия 4.1.2, 4.1.3, 4.1.4, 4.1.6, 4.1.7, 4.1.8 Рассмотрим следующие множества функций от п переменных: полиномы poly = {w : w = 0(пг), для некоторой t = const}, суперполиномы $uperpolya = {w : w = 0(п1оя'"п)} и субэкспопенциальные функции subexpa = {w : vj = 0(2" )}. Для них получены следующие иерархии:

|k/log2nj —NOBDDpoiy С k—NOBDDp0iy

[k/log2nJ — OBDDp0iy С к—OBDDp0iy,

где к = o(n/log2n).

Lk/loga+2nJ-NOBDDsuperpoly(l С k-NOBDDsuperpolyQ,

Lk/loga+2nJ — OBDDsuperpoiya С к— OBDDsuperpoiyQ, где к = о(п/ log2+1 п), а = const, а > 0.

[к/(na log2 n)J — NOBDDsubexPa С k-NOBDDsubexPo

Lk/(nalog2n)J-OBDDsubexPtt С k-OBDDsubexpa

1—a

где к = о(п;1о&п), 0<a<l-e,£ = const, e > 0.

Эти иерархии в детерминированном случае улучшают результаты Бол-линг и соавторов [2], а также в недетерминированном случае улучшают результаты, полученные для более общей модели в работе Окольнишниковой [5] и в работе Татачара [6].

Заметим, что данный метод не позволяет получить более точную иерархию.

Приведенные результаты были опубликованы в работах 4 и 8 из списка публикаций на тему диссертации.

Благодарности. Автор выражает искреннюю благодарность своему научному руководителю, доктору физико-математических наук, профессору Фа-риду Мансуровичу Аблаеву за постоянное внимание и неизменную поддержку данной работы.

Список литературы

1. Ajtai М. A Non-linear Time Lower Bound for Boolean Branching Programs //Theory of Computing. - 2005. - V. 1. -I. 1. - P. 149-176.

2. Boiling B. Hierarchy Theorems For kOBDDs And kIBDDs / B. Boiling, M. Sauerhoff, D. Sieling, I. Wegener // Theoretical Computer Science, 1998. - V. 205. - I. 1-2. - P. 45-56.

3. Borodin A. On lower bounds for read-k-times branching programs. / A. Borodin, A. Razborov, Smolensky R.// Computational Complexity, 1993. - V. 3 (1). - P. 1-18.

4. Hromkovich J. On the Power of Nondeterminism and Randomness for Oblivious Branching Programs. /J. Hromkovich, S. Martin// Theory of Computing Systems, 2003. - V.36.

- P. 159-182.

5. Okol'mshnikova E. On the hierarchy of nondeterministic branching k-programs./ E. Okol'nishnikova // 11th International Symposium volume of Fundamentals of computation theory. Lecture Notes in Computer Science, Springer, 1997. - V. 1102. - P. 376-387.

6. Thathachar J.S. On separating the read-k-times branching program hierarchy. / J. S. Thathachar // 30th ACM STOC, 1998. - P. 653-662.

7. Wegener I. Branching Programs and Binary Decision Diagrams: Theory and Applications / I. Wegener — Philadelphia: Society for Industrial and Applied Mathematics, 2000.

Публикации no теме диссертации Работы [1], [2] и [3] опубликованы в журналах, входящих в Перечень ВАК.

1. Ablayev F. Very Narrow Quantum OBDDs and Width Hierarchies for Classical OBDDs. / F. Ablayev, A. Gainutdinova, K. Khadiev, A. Yakaryilmaz. // Lecture Notes in Computer Science, Springer, 2014. - V. 8614. P. 53-64.

2. Ablayev F. Extension of the hierarchy for k-OBDDs of small width. / F. Ablayev, K. Khadiev. // Russian Mathematics, 2013. - V. 57 (3). - P. 46-50.

3. K. Khadiev. Width Hierarchy for k-OBDD of Small Width // Lobachevskii Journal of Mathematics, 2015- V. 36, - I. 2, - PP. 178-183

4. Аблаев Ф.М. Уточнение иерархии классов булевых функций, представимых в моделях k-OBDD ветвящихся программ / Аблаев Ф.М., Хадиев К.Р. // Материалы

XI Международного семинара "Дискретная математика и ее приложения", посвященный 80-летию со дня рождения академика О. Б. Лупанова, г. Москва, МГУ. — М.: Изд-во механико-математического факультета МГУ, 2012.

5. Хадиев К.Р. Расширение иерархии для стабильной k-OBDD / Хадиев К.Р. // Материалы X Международного семинара "Дискретная математика и ее приложения", г. Москва, МГУ. —- М.: Изд-во механико-математического факультета МГУ, 2010.

6. Хадиев К.Р. Иерархия классов булевых функций, представимых в детерминированных и недетерминированных моделях OBDD ветвящихся программ по параметру ширины. / Хадиев К.Р. // Проблемы теоретической кибернетики. Материалы XVII международной конференции. — Казань: Отечество, 2014.

7. Хадиев К.Р. Построение иерархии классов сложности булевых функций вычислимых детерминированными, недетерминированными и вероятностными k-OBDD/ Хадиев К.Р. // Дискретные модели в теории управляющих систем: IX Международная конференция, Москва и Подмосковье, 20-22 мая 2015 г.: Труды / Отв. ред. В.Б. Алексеев, Д.С. Романов, Б.Р. Данилов. — М.: МАКС Пресс, 2015.

8. Хадиев К.Р. Уточнение иерархии классов булевых функций, представимых в моделях k-OBDD ветвящихся программ. / Хадиев К.Р. // Проблемы теоретической кибернетики. Материалы XVII международной конференции. — Казань: Отечество, 2014.

9. Khadiev К. New Size Hierachies for Two-way Non-uniform Automata. / K. Khadiev, A. Yakaryilmaz // Sixth Workshop on Non-Classical Models of Automata and Applications (NCMA 2014) Short Papers, 2014. - P. 13-18.

10. Khadiev K. Width Hierarchy for k-OBDD of Small Width. // Electronic Colloquium on Computational Complexity (ECCC), 2015. - V. 021.

Подписано в печать 13.10.2015. Бумага офсетная. Печать цифровая. Формат 60x84 1/16. Гарнитура «Computer Modern». Усл. печ. л. 1,16. Тираж 150 экз. Заказ 112/10

Отпечатано с готового оригинал-макета в типографии Издательства Казанского университета

420008, г. Казань, ул. Профессора Нужина, 1/37 тел. (843) 233-73-59, 233-73-28