Курсовая работа: Оценки на коммуникационную сложность булевых функций и игр Карчмера Вигдерсона в разных моделях

Содержание

























2

• Введение

Определение 1. Формула в базисе Де Моргана для функции : {0, 1} → {0, 1} — это булевая формула с переменными { ₁, . . . , }, соответствующим отдельным битам вхо-да , и со связками (гейтами) {∧, ∨, ¬}, вычисляющая функцию . Законы Де Моргана позволяют нам предполагать, что все ¬ находятся непосредственно перед переменны-ми. Структура формулы Де Моргана представляет собой корневое дерево (листья со-ответствуют переменным, а внутренние вершины — логическим связкам). Размером формулы называется количество листьев, а глубиной формулы — высота дерева, т.е. количество рёбер в самом длинном простом пути от корня до некоторого листа.

Определение 2. Будем говорить, что семейство булевых функций : {0, 1} → {0, 1} вычисляется формулами Де Моргана размера ( ), если для каждого ∈ N существует формула Де Моргана размера ( ), вычисляющая . Формульной сложностью ( ) функции называется минимальная функция , такая что вычисляется формулами Де Моргана размера ( ).

Определение 3. Будем говорить, что семейство булевых функций : {0, 1} → {0, 1} вычисляется формулами Де Моргана глубины ( ), если для каждого ∈ N существу-ет формула Де Моргана глубины ( ), вычисляющая . Формульной глубиной ( ) функции называется минимальная функция , такая что вычисляется формулами Де Моргана глубины ( ).

Есть некоторая связь между этими двумя характеристиками.

Утверждение 1. Для любой булевой