О сложности сужений булевых функций Чашкин, Александр Викторович

Краткое описание

Чашкин, Александр Викторович.
О сложности сужений булевых функций : диссертация ... доктора физико-математических наук : 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. Экстремальные сужения.