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

Содержание


















2

Введение

Определение 1. Формула Де Моргана от переменных x₁, . . . , x_n — это двоичное дерево, где каждый лист помечен литералом {x₁, . . . , x_n, ¬x₁, . . . , ¬x_n } или кон-стантой {0, 1}, и каждая внутренняя вершина помечена логической связкой ∧ или ∨.

Будем говорить, что формула φ вычисляет булеву функцию f : {0, 1}n → {0, 1}, если для любого x ∈ {0, 1}ⁿ значение φ на входе x совпадает с f(x). Размером фор-мулы φ называется количество листьев, а глубиной формулы φ — высота дерева, т.е. количество рёбер в самом длинном простом пути от корня до некоторого листа.

Определение 2. Формульной сложностью L(f) функции f называется мини-мальная функция s, такая что f от n переменных вычисляется формулами Де Моргана размера s(n).

Определение 3. Формульной глубиной D(f) функции f называется минималь-ная функция d, такая что f от n переменных вычисляется формулами Де Мор-гана глубины d(n).

Эти два показателя эквивалентны с точностью до логарифмирования и умно-жения на константу (log₂ L(f) ≤ D(f) ≤ c ·log₂ L(f)), поэтому достаточно рассмат-ривать только что-нибудь одно, например, формульную сложность L(f).
Доказательство нижних оценок на формульную сложность булевых функций

— одна из центральных задач теории сложности вычислений, которой различные исследователи занимаются уже более 80 лет. Так, Шеннон и Риордан [14] методом подсчета доказали, что большая доля булевых функций от n переменных имеет формульную сложность хотя бы _log²ⁿ_n . Однако на протяжении последующих лет уче-ные, такие как Храпченко [8], Субботовская [16] и многие другие, занимались этой теорией, но для явных функций были доказаны только полиномиальные нижние оценки, лучшей из которых стала оценка Ω(n3) в работе Хостада [5] на формульную сложность функции Андреева [1], которая была придумана Нечипоруком [12].

работе [7] Карчмером и Вигдерсоном было замечено, что формулы в базисе Де Моргана тесно связаны с задачами коммуникационной сложности. Коммуни-кационная сложность — это мощный инструмент с приложениями в алгоритмах, схемной сложности, сложности доказательств и многих других областях теоретиче-ской информатики. В классической модели