О сложности сужений булевых функций

• Автор: Чашкин, Александр Викторович
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 1999
• Место защиты: Москва
• Количество страниц: 142 с.

СОДЕРЖАНИЕ
Введение
Глава 1. Пороговые суммы
1.1. Продолжение частичных функций
1.2. Теорема о пороговых суммах
1.3. Следствия теоремы о пороговых суммах
Глава 2. Сложность сужений булевых функций.
Схемы из функциональных элементов
2.1. Нижние оценки сложности сужений
2.2. Максимально сложные сужения
2.3. Функции с малым числом единиц
2.4. Экстремальные сужения
Глава 3. Схемы из функциональных элементов.
Свойства и применения сужений
3.1. Разложение булевых функций
3.2. Условия существования разложений
3.3. Сложность разложений
3.4. Самокорректирующиеся схемы, реализующие булевы функции полиномиального веса
3.5. Сложность и глубина схем, реализующих частичные булевы функции
Глава 4. Сложность сужений булевых функций.
Контактные схемы и формулы
4.1. Нижние оценки сложности сужений. Общая теорема
4.2. Нижние оценки сложности сужений для контактных
схем
4.3. Нижние оценки сложности сужений для формул

СОДЕРЖАНИЕ
Глава 5. Локальная сложность булевых функций
5.1. Определения
5.2. Операторы сжатия
5.3. Локально сложные функции
5.4. Локально простые функции
Глава 6. Неветвящиеся программы с условной остановкой. Среднее время вычисления значений булевых функций
6.1. Определения
6.2. Приведенные программы
6.3. Элементарные функции
6.4. Свойства среднего времени и свойства неветвящихся программ
Глава 7. Неветвящиеся программы с условной
остановкой. Сложность сужений
7.1. Функции Шеннона для среднего времени
7.2. Оценки числа программ
7.3. Нижние оценки среднего времени
7.4. Верхние оценки среднего времени
7.5. Частичные булевы функции
7.6. Сложность сужений
7.7. Экстремальные сужения
Глава 8. Вероятностные неветвящиеся программы с условной остановкой
8.1. Основные определения и понятия
8.2. Надежные вероятностные программы
8.3. Вероятностные программы с надежностью меньшей единицы
8.4. Общий случай
8.5. Экстремальные сужения
Литература
ВВЕДЕНИЕ
В диссертации изучается ряд вопросов относящихся к теории сложности булевых функций. Все рассматриваемые ниже задачи объединяет следующее обстоятельство: в каждой задаче целью или средством исследования являются сужения булевых функций. Цель работы заключается в выявлении роли сужений булевых функций в различных разделах теории сложности этих функций.
Каждое сужение, по своему определению, является частичной функцией. Интерес к частичным функциям возник достаточно давно и в течении последних тридцати лет оставался на достаточно высоком уровне. Исследовалась сложность частичных функций, определенных на областях различной мощности [1, 22]. Изучались приложения частичных функций к различным задачам теории сложности. Здесь прежде всего нужно отметить работы Э.И. Нечипорука [13] и А.Е. Андреева [2], касающиеся самокорректирующихся вычислений, в которых частичные функции играли существенную роль. Естественным образом частичные функции возникали при анализе различных вероятностных вычислений [18], приближенной реализации булевых функций [24]. Однако, как правило, частичные функции исследовались в шенноновской постановке: вводился некоторый класс частичных функций и изучалась сложность самых сложных функций из этого класса. В результате получались утверждения о самых сложных или о "почти всех" функциях данного класса.
Важной особенностью диссертации является то, что в ней изучаются не просто частичные функции, а сужения полностью определенных функций, т. е. частичные функции каждая из которых совпадает в своей области определения с какой-либо полностью определенной функцией. При таком подходе исходным объектом является полностью определенная булева функция. Другая особенность диссертации заключается в том, что полученные в ней утверждения справедливы, как правило, для всех функций. В частности оказалось, что у каждой булевой функции можно найти небольшое число сужений в которых содержится вся информация об исходной функции. Более точно, в диссертации показано, что для каждой булевой функции от те переменных существует простое разложение элементами которого являются ее сужения на не более чем те областей небольшой мощности. Наибольший интерес рассматриваемые разложения представляют в случае функций небольшой сложности, например по-

СХЕМЫ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ

постоянной, справедливы неравенства
ЧЛ < л
1о§(/61п(ЛГ(Л,п)|Л|)) + 1+18в
< ,61оё([£)|/(61п(АГ(£,?г)|Д|)) 1оё(с*/61п(ЛГ(Л,п)|Д|))
Лемма 2.1 доказана.
Лемма 2.2. Пусть Б С {0,1}п, / : Д —> {0,1}, М — такое целое, что 64(1оё(4|Л|/(1п(Я(Х(/),7г)|Л|))21п((Х(/),тг)|Л|) <М< |Д|. Положим (1 = М/2(1оё(4|Д|/(1п(1У(Л(/), п)|Д|))2. Допустим, что Л(/) >
Доказательство. Используем метод от противного. Предположим, что для любой области Л мощности М справедливо неравенство
Положим Л = та'кц<Щ'=м ЧЛи)' Будем считать, что Л < Л(/). В противном случае утверждение леммы тривиально. Легко видеть, что с1 > 321п(А(Л(/), тг|Д|)) и М > 2е£(1оё(4|Д|/й))2. Следовательно, последнее выключенное неравенство справедливо для любой области Л', размер которой не превосходит 2с?(1оё(4|Д|/е?))2. Поэтому можно воспользоваться леммой 2.1. Из этой леммы следует, что
Т , Гт 1оё(/61п(іУ(Л(/), та)|Д[)) и;б1оё(|Л|/1п(1У(Л(/),л)|Л|)) -1оёДО1п(#(£(/),п)1Д|)) 6]оё(|Л|/61п(1У(Л,тг)|Л[)) 61оё(|Л|/1п(Д(Л(/),та)|Л|)) 1оё(сг/61п(1У(Л,г!,)|Л|)) '
.61оё([Д|/б1п(1У(Л, та)|Л|))
1 ' 1о8(а/61п(ЛГ(Л,п)|Л|)) ’
ется область Л' такал, что
Тогда среди областей мощности М име-
ЦЬг) > л(/)
1оё(/61п(іУ(Л(/), тг) |Л |))
61оё(|Л|/ 1п(1У (Л(/), п)|Л |)) ’
ьш < ЧЛ
1о/61п(іУ(Л(/),п)|Л|))
61оё(|Л|/1п(1У(Л(/),п)|Л|))'
Т(П < т 61оё(| Л [/(б 1п(А1(Л, тг) 1Д |)) 1оё(й/61п(ЛГ(Л,п)|Л|)) '
Но тогда в силу сделанного предположения имеем