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

1. Введение 3
2. Основные определения 6
2.1. Классическая коммуникационная сложность 6
2.2. Игры Карчмера — Вигдерсона 8
3. Полудуплексная коммуникационная сложность 8
3.1. Методы доказательства нижних оценок 9
3.2. Оценки на функцию дизъюнктности 11
3.3. Оценки на игры Карчмера — Вигдорсона 14
3.4. Оценки на функцию “больше” 19
3.5. Недетерминированная полудуплексная сложность 21
4. Сжатие протоколов 23
5. Вычисления с оракулом 27
5.1. Формальная модель 29
5.2. Оракул единичного расстояния Хэмминга 30
5.3. Оракул точного расстояния Хэмминга равного I 35
5.4. Верхняя оценка 36
5.5. Оракул однобитового равенства 37
6. Заключение 39
Список литературы 39
A. Перевешивания 42
B. Универсальное отношение 43
Купить

Определение 1. Формула в базисе Де Моргана для функции f: {0,1}п ^ {0,1} — это булевая формула с переменными {т1,... ,хп}, соответствующим отдельным битам вхо­да f, и со связками (гейтами) {Л, V, —}, вычисляющая функцию f. Законы Де Моргана позволяют нам предполагать, что все — находятся непосредственно перед переменны­ми. Структура формулы Де Моргана представляет собой корневое дерево (листья со­ответствуют переменным, а внутренние вершины — логическим связкам). Размером формулы называется количество листьев, а глубиной формулы — высота дерева, т.е. количество рёбер в самом длинном простом пути от корня до некоторого листа.
Определение 2. Будем говорить, что семейство булевых функций fn : {0,1}п ^ {0,1} вычисляется формулами Де Моргана размера s(n), если для каждого п Е N существует формула Де Моргана размера s(n), вычисляющая fn. Формульной сложностью L(f) функции f называется минимальная функция s, такая что f вычисляется формулами Де Моргана размера s(n).
Определение 3. Будем говорить, что семейство булевых функций fn : {0,1}п ^ {0,1} вычисляется формулами Де Моргана глубины d(n), если для каждого п Е N существу­ет формула Де Моргана глубины d(n), вычисляющая fn. Формульной глубиной D(f) функции f называется минимальная функция d, такая что f вычисляется формулами Де Моргана глубины d(n).
Есть некоторая связь между этими двумя характеристиками.
Утверждение 1. Для любой булевой функции f верно
log2 L(f) < D(f) < 1.821°§2 L(f )•
Первое неравенство верно в силу того, что размер двоичного дерева не больше чем 2d, где d — глубина дерева. Второе неравенство верно, так как формулы можно сбалан­сировать с небольшим увеличением глубины (подробнее см. в [Juk12]).
Доказательство оценок на сложность булевых формул и схем является одной из основных задач в теории сложности вычислений. Еще в 1942 году Риордан и Шеннон [RS42] показали, что если выбрать булевую функцию от п переменных случайно, то с вероятностью близкой к 1 она будет иметь формульную сложность не менее 2п/ log п. Но до сих пор неизвестны явно заданные функции из классов P или NP большой сложности.
На протяжении более 40 лет разрабатывались методы доказательства нижних оце­нок, начиная с работ Субботовской [Sub61] и Храпченко [Khr71], вплоть до знаменитой работы Хостада [Has98]. В итоге, удалось достичь кубической нижней оценки на фор­мульную сложность явной булевой функции (функция Андреева). Эту нижнюю оценку не удаётся превзойти уже более 20 лет. Результат Хостада был улучшен Талом [Tal14], но улучшение касается только членов второго порядка.
Карчмер, Раз и Вигдерсон [KRW95] предложили подход для доказательства супер­полиномиальной нижней оценки на размера формулы для булевых функций из класса P (из этого следовало бы P Е NC1). Предлагаемый подход заключается в доказа­тельстве нижних оценок на глубину блочной композиции двух произвольных булевых функций (KRW гипотеза).
Определение 4. Пусть f : {0,1}т > {0, 1} и д : {0,1}п ^ {0,1} - булевые функции. Блочная композиция f о д : ({0,1}п)т ^ {0,1} определяется как
(f о д)(Х1,...,хт) = f (g(xi),...,g(xm))i
где xi,... ,xm Е {0,1}п.
Гипотеза 1 (KRW гипотеза). Пусть f : {0,1}m ^ {0,1} и д : {0,1}п ^ {0,1} — неконстантные функции. Тогда
D(f од) и D(f) + D(g).
Теорема 1. Если KRW гипотеза верна, то P Е NC1.
Доказательство. Рассмотрим функцию h : {0,1}п х {0,1}п ^ {0,1}, которая на вход принимает таблицу истинности функции f : {0,1}logп ^ {0,1} и строку x, и вычисляет значение блочной композиции log п/ log log п функций f на входе х:
h(f,x) = (f о^уо f)(х).
log п/ log log п
Нетрудно заметить, что h Е P. Чтобы показать, что h Е NC1, обозначим через f функцию c максимальной глубиной формулы. Из теоремы Риордана — Шеннона f имеет глубину log п. Тогда f о • • • о f имеет глубину примерно в log п • (log п/ log log п) = w(log п), следовательно, f о • • • о f Е NC1. Любая формула для h должна вычислять f о • • • о f, если мы в качестве f подставим f, поэтому h Е NC1. □
Стоит отметить, что это доказательство будет работать даже при условии более слабой версии гипотезы KRW, например D(f о д) > D(f) + е • D(g) или D(f о д) > е • D(f) + D^) для некоторых е > 0.
Основным подходом к доказательству KRW гипотезы является коммуникационная сложность. В данной работе рассматривается коммуникационная сложность булевых функций и отношений Карчмера — Вигдерсона [KW88]. Вместе с классической ком­муникационной сложностью, введенной Яо [Yao79], рассматриваются полудуплексные модели коммуникационной сложности, рассмотренные в статье [HIMS18b], а также ком­муникационная сложность с оракулом EHDi и EQ.
В классической коммуникационной сложности Алиса и Боб пытаются вычислить некоторую функцию f (x,^), при условии, что Алиса знает только функцию f и вход x, а Боб функцию f и вход ^. Игроки могут общаться, посылая биты друг другу, по одному биту за раунд, и в конце общения оба игрока должны знать результат f (x,^). Существенным свойством этой классической модели является то, что в каждом раунде общения один игрок отправляет бит, а другой его получает.
Существует множество расширений этой модели коммуникации, таких как рандоми­зированная коммуникационная сложность, недетерминированная коммуникационная сложность [KN97], различные типы моделей коммуникации с несколькими игроками [CFL83] и другие. В [HIMS18b] авторы предложили рассмотреть модель коммуникации, в которой игроки разговаривают по полудуплексному каналу связи. Хорошо известным примером полудуплексной коммуникации является связь с использованием рации: один игрок удерживает кнопку “push-to-talk”, чтобы поговорить с другим игроком, который в свою очередь держит ее отпущенной, чтобы слушать. Если два человека пытаются говорить одновременно, тогда они не слышат друг друга. Формально говоря, в каждом раунде каждый игрок выбирает одно из трех действий: отправить 0, отправить 1 или получить. Существует три различных типа раундов: классический раунд, когда один игрок отправляет некоторый бит, в то время как другой получает, потерянный раунд, когда оба игрока отправляют биты (эти биты теряются), и тихий раунд, когда оба иг­рока получают. В [HIMS18b] авторы определили три варианта полудуплексной модели, основанные на том, что происходит в тихом раунде, мы рассмотрим данную модель в разделе 3.
Еще одним вариантом расширения является коммуникационная модель с оракулом [BFS86]. Теперь игроков трое: Алиса, Боб и Чарли, выполняющий роль оракула. Алиса и Боб каждый раунд отправляют Чарли по одному биту или нескольким сразу. Чарли по ним вычисляет некоторую функцию А(а, Ь) и говорит ответ. Цель игроков с данным оракулом А вычислить функцию /(х, у). В разделе 5 мы подробнее рассмотрим данную модель.
Целью данной работы является доказательство оценок на формульную сложность булевых функций с использованием коммуникационной сложности.
Обзор результатов:
1. В разделах 3.2, 3.3, 3.4 мы докажем оценки на функции DISJ, GT, игры Карчмера — Вигдерсона для функций MODp в различных полудуплексных моделях.
2. В 3.5 рассмотрим недетерминированную полудуплексную сложность и покажем её связь с классической моделью.
3. В главе 4 рассмотрим технику случайных ограничений для обобщенных игр Карч- мера — Вигдерсона.
4. В разделе 5.2 мы докажем оценку на функцию EHD^ c оракулом EHDi.
5. В разделе 5.3 докажем оценку на функцию EHD& c оракулом EHDi при к > I.
6. В разделе 5.4 покажем как с помощью оракула HD 7. В разделе 5.5 рассмотрим оракул однобитового равенства, докажем, что случайная функция имеет сложность п — о(п), покажем точную оценку на функцию EHD1.
Купить