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

brief description

Хадиев Камиль Равилевич. Анализ сложности вычисления булевых функций ветвящимися программами с ограничениями.: диссертация ... кандидата физико-математических наук: 01.01.09 / Хадиев Камиль Равилевич;[Место защиты: Казанский (Приволжский) федеральный университет].- Казань, 2015.- 132 с.

КАЗАНСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ
На правах рукописи УДК ххх. ххх
Хадиев Камиль Равилевич
Анализ сложности вычисления булевых функций ветвящимися
программами с ограничениями.
Специальность 01.01.09 — «дискретная математика и математическая кибернетика»
Диссертация на соискание учёной степени кандидата физико-математических наук
Научный руководитель: доктор физико-математических наук, профессор
Аблаев Ф. М.
Казань — 2015

2
Оглавление
Введение 4
1 Коммуникационное моделирование &-OBDD 11
1.1 Детерминированная модель 11
1.1.1 Нижние оценки 11
1.1.2 Доказательство теоремы 1.1.3 14
1.1.3 Иерархия классов сложности 23
1.2 Недетерминированная модель 31
1.2.1 Нижние оценки 31
1.2.2 Доказательство теоремы 1.2.1 32
1.2.3 Иерархия классов сложности 39
1.3 Вероятностная модель 40
1.3.1 Нижние оценки 40
1.3.2 Доказательство теоремы 1.3.1 42
1.3.3 Иерархия классов сложности 56
1.4 к раз читающие забывающие ветвящиеся программы 58
1.4.1 Определения 58
1.4.2 Детерминированная модель "малой" ширины 60
1.4.3 Недетерминированная модель "малой" ширины 68
1.4.4 Вероятностная модель "малой" ширины 72
2 Иерархия по ширине для 1-OBDD и &-OBDD 77
2.1 Иерархия для OBDD "малой" ширины 77
2.1.1 Доказательство теоремы 2.1.1 78
2.1.2 Доказательство теоремы 2.1.4 79
2.2 Иерархия для OBDD "большой" ширины 82

з
2.2.1 Доказательство теоремы 2.2.4 86
2.2.2 Сравнение результатов для "малой" и "большой" ширины. . . 88 2.3 к раз читающие забывающие ветвящиеся программы. Иерархия по
ширине 88
2.3.1 Детерминированная модель 88
2.3.2 Недетерминированная модель 89
2.3.3 Вероятностная модель 91
3 Двухсторонние автоматы с переменной структурой 94
3.1 Определения 94
3.2 Детерминированный двухсторонний автомат с переменной струк¬турой 99

3.2.1 Нижняя оценка для 2DAn и 2DA® 100
3.2.2 Иерархия классов сложности 102
3.3 Недетерминированный двухсторонний автомат с переменной
структурой 111
3.3.1 Нижняя оценка для 2NAn и 2NA® 111
3.3.2 Иерархия классов сложности 113
4 Функциональное представление &-OBDD 116
4.1 Теорема об иерархии 116
4.2 Эмуляция k-OBDD с помощью NOBDD 119
4.3 Доказательство теоремы 4.1.1 121
4.4 Ограничения метода 125
Заключение 126
Список литературы 128

bibliography

Заключение.
В работе исследованы известные модели для представления булевых функ-ций — OBDD, k-OBDD: детерминированные, недетерминированные и вероят-ностные модели, а также двухсторонние детерминированные и недетерминиро-ванные автоматы с переменной структурой.
В главе 1 рассмотрена техника, основанная на коммуникационных вычис-лениях и направленная на оценку числа подфункций для булевой функции. Эта техника позволила построить нижние оценки для классов сложности раз-личных моделей. Кроме того, в главе 2 получены нижние оценки для OBDD, которые также направлены на оценку числа подфункций.
Благодаря коммуникационной технике в разделе 1.4 главы 1 получены иерар¬хии классов булевых функций, распознаваемых k-OBDD, k-NOBDD и k-POBDD "малой" ширины (менее чем линейная) по параметру к.
Кроме того, в главе 4 была рассмотрена техника функционального представ¬ления &-OBDD, с помощью которой доказана вторая группа нижних оценок. С помощью полученных нижних оценок удалось доказать результаты относи¬тельно иерархии для &-OBDD, &-NOBDD "большой" ширины (полиномиальной, суперполиномиальной, субэкспоненциальной).
Таким образом, эти две группы результатов дополняют друг друга и поз-воляют построить иерархии для широкого спектра вариантов ширины: от кон-стантной до субэкспаненциальной.
В разделе 2.3 главы 2 с помощью коммуникационного подхода были получе¬ны иерархии по ширине для &-OBDD, &-NOBDD и &-POBDD "малой" ширины. В дополнение к этому в главе 2 получены иерархии для 1-OBDD и 1-NOBDD по ширине для случаев "большой" и "малой" ширины.

127
Коммуникационный подход также был применен для двухсторонних авто-матов с переменной структурой, в результате чего в главе 3 получены иерар-хии по количеству состояний для детерминированного и недетерминированного случая.
Естественным продолжением полученных результатов может быть:
— получение иерархии классов булевых функций, вычислимых &-POBDD "большой" ширины.
— исследование классов булевых функций, вычислимых кванотвыми версия¬ми моделей &-OBDD и двухсторонних автоматов с переменной структурой.
получение иерархии классов языков, распознаваемых классичискими вер-сиями двухсторонних автоматов.