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

• Автор: Забалуев, Руслан Николаевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Москва
• Количество страниц: 74 с. : ил.

Глава 1 О средней сложности полиномов Жегалкина

1.1 Схемная сложность полиномов Жегалкина

1.1.1 Прямоугольное представление полиномов

1.1.2 Реализация однородных полиномов

1.1.3 Реализация полиномов Жегалкина

1.2 Нижние оценки средней сложности

1.3 Верхние оценки средней сложности

Глава 2 О средней сложности монотонных функций

* 2.1 Вспомогательные утверждения о монотонных функциях

2.2 Об одном разбиении множества двоичных наборов

2.3 Верхняя оценка

2.4 Нижние оценки
Глава 3 О средней сложности функций из инвариантных классов
3.1 Ненулевые инвариантные классы
3.2 Нулевые инвариантные классы
Глава 4 О реализации функций О-программами
4.1 Оценка числа О-ирограмм
4.2 Оценки средней О-сложности
Литература

В настоящей диссертации рассматривается сложность реализации булевых функций из некоторых классов неветвящимися программами с условной остановкой.
Рассматриваемые программы были введены А. В. Чашкиным [13]. Они обобщают понятие схемы из функциональных элементов и являются естественной моделью неветвящихся вычислений, т. е. вычислений в которых нет условного перехода и косвенной адресации, но есть возможность досрочного прекращения работы при выполнении определенного условия. Такие вычисления можно представить следующим образом. Вычисления выполняет процессор, снабженный памятью, состоящей из отдельных ячеек. Эти ячейки будем обозначать символами у. В памяти выделяется особая ячейка, со-• держимое которой объявляется результатом работы программы. Эта ячейка
обозначается символом г. Процессор работает под управлением программы, являющейся последовательностью вычислительных команд и команд остановки. Каждая вычислительная команда за единицу времени вычисляет значение некоторой двуместной булевой функции, аргументами которой являются величины, содержащиеся в определенных ячейках памяти. Вычисленный результат также помещается в одну из ячеек памяти. Команда остановки может прекратить выполнение программы. Каждая такая команда имеет единственный аргумент - содержимое некоторой ячейки памяти. Если значение аргумента равно единице, то процессор прекращает работу. Если значение аргумента равно нулю, то выполняется следующая команда программы. Естественной мерой сложности таких программ является среднее по всем возможным аргументам время работы (средняя сложность).
В многочисленных работах А. В. Чашкина были исследованы различные

вопросы, связанные со средней сложностью. В частности, исследованы: средняя сложность конкретных функций и "почти"всех функций [13, 14, 15], средняя сложность частичных функций и частичных функций данного веса [16], средняя сложность симметрических функций [17].
В данной работе исследуются схемная и средняя сложность булевых функций, заданных полиномами Жегалкина, средняя сложность функций из инвариантных классов, средняя сложность монотонных функций. Часть работы посвящена вычислению функций неветвящимися программами с условной остановкой, допускающими только однократное использование промежуточных значений.
Сформулируем понятия и обозначения, используемые в диссертации. Некоторые из вводимых понятий носят описательный характер. Их точные определения будут даны в соответствующих главах диссертации.
Пусть Р2(2) — множество всех не более чем двуместных булевых функций, X = {дц тп} — множество независимых булевых переменных. Введем
множество У = {У1, ..., уп} и переменную г. Переменные из множества У
назовем внутренними, а переменную г — выходной переменной. Пусть, далее, а £ У и {г}, Ъ,с € X и У и {г}, / 6 Рг(2). Вычислительной командой р назовем выражение
р: а = /(Ь,с), (1)
переменную а назовем выходом этой команды, а величины Ъ, с — ее входами. Если переменная а является выходом команды р, то будем говорить, что команда р изменяет значение этой переменной, а если а не является выходом р, то будем говорить, что команда р не изменяет ее значение. Командой остановки р назовем выражение
р: ^ор(б), (2)
а переменную Ь назовем входом этой команды.

в силу монотонности функций, краткое значение ДДФо4Д функции предка на наборе а совпадает с этими значениями.
Для каждого j = 1 определим функцию зДад,хп) следующим образом:
1, если /цДсДщД — /2,Дфо2,з) — ■■■ — О, в ином случае.
Лемма 9. Если = 1, тогда для функции /(ад, ...,а:п) 6 М(п) справедливо равенство
/(*) = /и(^1,ДДоказательство. Так как вДст) = 1, то краткие значения на наборе <5 всех функций из множества Bj совпадают:
/рДСми) — /г.Дфиг.з')
Функция & В]-1 (г = 1, ...,2^'-1) является предком для функций /2г-1Д
и /2г>г Значит, верны соотношения
/г Д-1 ) — /2»—1,а (^ги2*-1 ^ ) = /2* Д (фиг
Откуда следует, что для функций из множества Д?_1 справедливы равенства
/1,7-1 (%л) = /2р-1 (^№2,3-1) = •" = /У-10 —1 (^ш23-1,з_1) = /10(^1,з)-
Таким образом, краткие значения на наборе а функций из множества Д_1 совпадают между собой и равны значению /рДст,^)- Поэтому выполнено
/цДФз)!,,) = /1,^-1 (^1,3-1) = "• = /1,1 (^Ш1д) = /(^)-
Лемма 9 доказана.