Доказательство нижних оценок на размер формул для булевых функций методами коммуникационной сложности тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат наук Смаль Александр Владимирович

• Смаль Александр Владимирович
• кандидат наук
• 2022

Оглавление диссертации кандидат наук Смаль Александр Владимирович

Введение

Глава 1. Основные определения

1.1 Список используемых обозначений

1.2 Классическая теория информации

1.2.1 Энтропия Шеннона

1.2.2 Взаимная информация

1.3 Коммуникационная сложность

1.3.1 Классическая модель для двух игроков

1.3.2 Нижние оценки

1.3.3 Изучаемые функции

1.3.4 Недетерминированная коммуникационная сложность

1.4 Связь коммуникационных протоколов и формул Де Моргана

1.4.1 Игры Карчмера —Вигдерсона

1.4.2 Теоретико-информационный подход к доказательству нижних оценок на размер коммуникационных протоколов

1.4.3 Гипотеза Карчмера —Раза —Вигдерсона

1.4.4 Универсальное отношение и отношение мультиплексера

Глава 2. Предсказание на основе частичной информации

2.1 Введение

2.2 Идеи, на которых основано доказательство

2.3 Предсказание семействами сертификатов

2.4 Предсказание семействами попарно несовместимых свидетелей

Глава 3. Полудуплексная коммуникационная сложность

3.1 Введение

3.2 Мотивация для изучения полудуплексных моделей

3.3 Полудуплексные модели

3.4 Общие оценки

3.5 Верхние оценки на полудуплексную коммуникационную

сложность функций

3.5.1 Полудуплексная коммуникация с тишиной

3.5.2 Полудуплексная коммуникация с нулём

3.5.3 Полудуплексная коммуникация с противником

3.6 Нижние оценки на полудуплексную коммуникационную сложность функций

3.6.1 Метод прямоугольников

3.6.2 Метод элиминации раундов

3.7 Обзор известных оценок на полудуплексную коммуникационную сложность функций

3.8 Оценки на полудуплексную коммуникационную сложность игр Карчмера —Вигдерсона

3.8.1 Верхние оценки

3.8.2 Нижние оценки

Глава 4. Гипотеза XOR-KRW и композиция универсального

отношения с функцией

4.1 Гипотеза XOR-KRW

4.2 Обзор методов и результатов

4.3 Полудуплексная коммуникационная сложность

4.4 Нижняя оценка на коммуникационную сложность

задачи Un Ш MUXn

4.4.1 Общий план доказательства

4.4.2 Первая стадия

4.4.3 Вторая стадия

4.4.4 Доказательство технической леммы

4.5 Нижняя оценка на коммуникационную сложность

задачи Un Ш KWg

4.5.1 Нижняя оценка на полудуплексную коммуникационную сложность задачи Un Ш MUXn

4.5.2 Связь нижних оценок на классическую коммуникационную сложность задачи Un Ш

и полудуплексную коммуникационную сложность

задачи Un Ш MUXn

4.5.3 Связь нижних оценок на классическую

коммуникационную сложность задачи ип Ш KWg

и частично полудуплексную коммуникационную

сложность задачи ип Ш МиХп

4.6 Нижняя оценка на блочную композицию универсального отношения и функции

4.7 Нижняя оценка на композицию произвольной функции

и функции мультиплексера

Заключение

Список литературы

Введение

Введение диссертации (часть автореферата) на тему «Доказательство нижних оценок на размер формул для булевых функций методами коммуникационной сложности»

Актуальность темы и степень её разработанности.

Определение. Формула Де Моргана ф от п переменных — это корневое двоичное дерево с пометками, в котором каждая внутренняя вершина имеет ровно два потомка и помечена одной из логических связок {Л, V}, а листья помечены литералами {х\,х2,... ,ХП,—Х\,—Х2,... ,—хп}. Вычисление формулы ф на входе х € {0,1}п заключается в подстановке значений соответствующих битов х в листья и последовательном вычислении значений для каждой внутренней вершины от листьев к корню в соответствии с пометками в этих вершинах. Значение формулы ф на входе х определяется как значение в корне, полученное в результате вычисления ф на х. Будем говорить, что формула ф вычисляет булевую функцию /п : {0,1}п ^ {0,1}, если для всех х € {0,1} значение ф на входе х совпадает с /п(х). Размером формулы ф называется количество листьев, а глубиной формулы ф — высота дерева, т.е. количество рёбер в самом длинном простом пути от корня до некоторого листа.

В дальнейшем под булевой функцией / : {0,1}п ^ {0,1}, если п не зафиксировано явно, будет подразумеваться бесконечная последовательность функций ..., где для любого % € М, : {0,1} ^ {0,1}.

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

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

Эти две характеристики булевых функций тесно связаны.

Утверждение. Существует такая константа с > 1, что для любой булевой функции f : {0,1}п ^ {0,1} выполняется

log2 L(f) ^ D(f) ^ с • log2 L(f).

Первое неравенство верно в силу того, что высота двоичного дерева ограничена снизу двоичным логарифмом от числа листьев. Второе неравенство имеет место, т.к. формулы Де Моргана можно сбалансировать с небольшим увеличением размера (подробнее см. [20]).

Доказательство нижних оценок на формульную сложность булевых функций—это одна из классических задач теории сложности вычислений. Ещё в 1942 году Риордан и Шеннон [32] доказали, что почти все булевы функции от п переменных имеют формульную сложность не менее 2n/ log п.

Теорема (Риордан, Шеннон). Для любого £ > 0 доля функций f : {0,1 }п ^ {0,1}, для которых L(f) ^ (1 — £) • 2п/ log п, не превосходит 2-2"^(£-о(1)).

Другими словами, если выбрать функцию случайно, то с вероятностью близкой к единице она будет иметь экспоненциальную формульную сложность. Однако неизвестно явно заданных функций (из классов P или NP) большой сложности. Более сорока лет исследователи развивали методы для доказательства нижних оценок: начиная с работ Субботовской [4] и Храпченко [5] вплоть до знаменитой статьи Хостада [15], в которой он доказал кубическую нижнюю оценку на формульную сложность функции Андреева [1; 3]. Эту нижнюю оценку не удаётся превзойти уже более 20 лет. Результат Хостада был улучшен Талом в работе [35], но улучшение коснулось только членов второго порядка, т.е. оценка осталась кубической.

Если изначальный подход к формульной сложности можно охарактеризовать как комбинаторный, то в дальнейшем стали появляться альтернативные методы анализа. В работе [22] Карчмером и Вигдерсоном было замечено, что формулы в базисе Де Моргана имеют очень тесную взаимосвязь с задачами коммуникационной сложности, предложенной Яо [37] за 10 лет до этого для совершенно других целей. В частности эта взаимосвязь позволяет получать оценки на формульную сложность и формульную глубину булевых функций через доказательство оценок на размер и глубину коммуникационных протоколов. В дальнейшем была сформулирована гипотеза Карчмера — Раза — Вигдерсо-на [21] и предложен план исследований, реализация которого может привести к

доказательству суперкубической или даже суперполиномиальной нижней оценки на формульную сложность явной булевой функции. Первые шаги этого плана были реализованы в работах [10; 11; 14; 16]. Основной инструментарий этих работ —это изучение коммуникационной сложности и теоретико-информационные методы.

Целью данной работы является разработка и совершенствование новых подходов к доказательству нижних оценок на формульную сложность булевых функций с использованием методов коммуникационной сложности.

Научная новизна. Все полученные результаты являются новыми. Теоремы о предсказании семействами сертификатов и попарно несовместных свидетелей улучшают известные до этого оценки, делая их точными. Идея рассмотрения полудуплексных моделей коммуникации является новой. Все полученные верхние и нижние оценки на полудуплексную коммуникационную сложность до этого были неизвестны. Основной результат последней главы про нижнюю оценку на композицию универсального отношения и некоторой функции является первой нетривиальной оценкой такого рода. Кроме самих результатов, новыми являются представленные в последней главе методы доказательства нижних оценок на коммуникационную сложность, основанные сведениях между задачами классической, недетерминированной и полудуплексной коммуникации.

Теоретическая и практическая значимость. Диссертация имеет теоретический характер. Полученные результаты и разработанные методы могут быть использованы для дальнейшего изучения формульной сложности булевых функций и коммуникационной сложности.

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

Основные положения, выносимые на защиту:

1. Доказано, что если случайная величина X, распределённая на {0,1}п, имеет энтропию Н(X) ^ п — к, то средняя вероятность того, что в X встречается сертификат для Х^ размера д < п не превосходит к . (Теорема 2.5)

2. Доказаны верхние оценки на полудуплексную коммуникационную сложность для функции равенства EQn: п/ log2 5 + п) для модели с тишиной и п/ log2 3 + п) для модели с нулём, а также верхняя оценка п/2 + 0(1) на функцию дизъюнктности БТ8Лп в модели с тишиной. (Теоремы 3.9, 3.12 и 3.10)

3. Доказаны нижние оценки на полудуплексную коммуникационную сложность функции внутреннего произведения п/2 для модели с тишиной, п/1.39 для модели с нулём и п/ ^2(7/3) для модели с противником. (Теоремы 3.23, 3.25 и 3.29)

4. Доказаны верхние оценки на количество информации, которым игроки могут обменяться за один раунд полудуплексной коммуникации: 2 бита в модели с тишиной и 1.389 бита в модели с нулём. Для случая, когда частные распределения на входах игроков являются независимыми, доказаны более сильные оценки: 1.67 бита в модели с тишиной и 1.234 бита в модели с нулём. На основе этого доказаны нижние оценки на полудуплексную коммуникационную сложность игр Карчмера — Вигдерсона для функций подсчёта. (Теоремы 3.34, 3.35 и 3.37)

5. Доказана нижняя оценка 1.5п — о(п) на коммуникационную сложность композиции универсального отношения и некоторой функции для случаев ХОЯ-композиции и блочной композиции. (Теоремы 4.12 и 4.33)

Достоверность полученных результатов обеспечивается их публикацией в рецензируемых научных изданиях, индексируемых международными базами данных.

Апробация работы. Основные результаты работы докладывались и обсуждались на следующих семинарах и конференциях.

1. Семинар по теории сложности в Санкт-Петербургском отделении Математического института им. В.А. Стеклова РАН (Россия, 2018 и 2020).

2. Традиционная зимняя сессия МИАН-ПОМИ, посвященная теме «Математическая логика» (Россия, 2018).

3. Международная конференция «The 29th International Symposium on Algorithms and Computation» (Тайвань, 2018).

4. Семинар по теории сложности в Математическом институте Чешской академии наук (Чехия, 2018 и 2021).

5. Семинар «Laboratoire d'Informatique, de Robotique et de Microelectro-nique de Montpellier» (Франция, 2019).

6. Колмогоровский семинар по сложности вычислений и сложности определений (онлайн, 2020).

7. Международная конференция «The 47th International Conference on Current Trends in Theory and Practice of Computer Science» (онлайн, 2021).

8. Международная конференция «The Computational Complexity Conference» (онлайн, 2021).

Публикации. Основные результаты по теме диссертации изложены в четырёх работах [8; 18; 27; 34], все из которых изданы в журналах, рекомендованных ВАК, и индексируемых Web of Science и Scopus.

Личный вклад. В работе [34] постановка задачи принадлежит соавтору. Обсуждение идей, которые могут использоваться в доказательстве, велось совместно. Автору принадлежит доказательство теоремы 2, являющейся основным результатом статьи. В работе [18] постановка задачи, основные определения, а также доказательства теорем 6-9, 15, 20 и 23 были разработаны совместно с И.А. Михайлиным. Кроме этого, автору принадлежат теоремы 14, 16 и 19. В работе [8] автору принадлежат постановка задачи и теорема 4. В работе [27] постановка задачи принадлежит соавтору. Автору принадлежит доказательство теоремы 9. Схема доказательства основных результатов была выработана авторами совместно.

Объем и структура работы. Диссертация состоит из введения, четырёх глав и заключения. Полный объём диссертации составляет 114 страниц, включая 1 рисунок и 5 таблиц. Список литературы содержит 37 наименований.

В первой главе даются все определения и результаты, необходимы для понимания представленных результатов. Во второй главе представлены оценки на предсказание семействами сертификатов и семействами попарно независимых свидетелей, опубликованные в [33; 34]. В третьей главе описываются полудуплексные модели коммуникационной сложности и доказывается ряд верхних и нижних оценок на сложность функций и отношений Карчмера —Вигдерсона

в этих моделях. Результаты третьей главы опубликованы в работах [8; 9; 18]. В четвёртой главе доказывается нетривиальная нижняя оценка на ХОЯ-ком-позицию универсального отношения и отношения Карчмера — Вигдерсона для некоторой функции, опубликованная в работе [27].

Глава 1. Основные определения

Материал разделов 1.2 и 1.3 излагается в соответствии с [2]. Информация раздела 1.4 является компиляцией материалов из различных источников с явным их указанием.

1.1 Список используемых обозначений

В этой работе используются следующие обозначения.

— [к] для к Е N обозначает множество {1,... ,к}.

— х о у для х,у Е {0,1}п обозначает конкатенацию строк х и у.

— х 0 у для х,у Е {0,1}п обозначает побитовое применение операции исключающее ИЛИ (XOR):

Ух,у Е{0,1}п, У Е [п] : (х 0 у)г = хг 0 уг.

— ni(S), где S является множеством кортежей одинаковой длины, обозначает проекцию S на координату г:

nt(S) = {ег | 3ei,... ,ei_i,ei+i,... : (еь ... ,ег—i ,ег,ег+1,...) Е S}.

— Логарифм без явного указания основания log п обозначает логарифм по основанию 2.

1.2 Классическая теория информации

1.2.1 Энтропия Шеннона

Энтропия Шеннона определяет количество информации Н(а) в распределении вероятностей для некоторой случайной величины а, принимающей значения из конечного множества.

Определение 1.1 (Шеннон, 1948). Пусть случайная величина а принимает значения из множества {а\,а2,... ,ак} с вероятностями {р\,р2,... ,Рк}, Pi ^ 0, Y^i Pi = 1. Энтропия Шеннона случайной величины а определяется как

к 1 Н(а) = У2Рг • log-

л Р г

г=\ 1 1

(при pi = 0 мы полагаем в этой сумме рг • log 1 = 0).

Утверждение 1.2. Для энтропии Шеннона выполняются следующие соотношения.

— H (а) ^ 0, причём H (а) = 0 тогда и только тогда, когда распределение случайной величины а вырождено.

— H (а) ^ log к, причём H (а) = log к тогда и только тогда, когда случайная величина а распределена равномерно.

Энтропию совместного распределения пары случайных величин а и в будем обозначать H (а, в).

Утверждение 1.3. Выполняются следующие свойства.

— H (а, в) ^ H (а)+ H (в), причём равенство достигается тогда и только тогда, когда случайные величины независимы.

— H (а) ^ H (а, в), причём равенство достигается тогда и только тогда, когда в полностью определяется значением а, т.е. в = f (а).

Определение 1.4. Энтропия а при условии события в = bj определяется следующим соотношением:

Н(а | р = Ь,) = Ç Рг[а = * | Р = У • log рг[а = 11 в = ц.

Определение 1.5. Условная (относительная) энтропия а относительно в определяется следующим соотношением:

H (а | в) = ^ Рг[в = bj ] • H (а | в = bj ).

j

Другими словами,

H (а | в) = Л E [Н (а | в = Ь3 )].

bj ^р

Утверждение 1.6. Условная энтропия обладает следующими свойствами.

- Н(а | в) ^ 0.

- Н(а | в) = 0 тогда и только тогда, когда а = /(в).

- Н(а,в) = Н(в) + Н(а | в) = Н(а) + Н(в | а).

Следствие 1.7. Н(а,в) ^ Н(а), причём равенство достигается тогда и только тогда, когда в = /(а).

1.2.2 Взаимная информация

Определение 1.8. Информация в а о величине в (взаимная информация случайных величин а и в) определяется следующим соотношением:

I(а : в) = Н(в) - Н(в | а).

Утверждение 1.9. Для взаимной информации выполняются следующие соотношения.

1. I(а : в) < Н(а).

2. I(а : в) < Н(в).

3. I(а : а) = Н(а).

4. I(а : в) = I(в : а).

5. I(а : в) = Н(а) + Н(в) - Н(а,в).

Определение 1.10. Пусть а,в,У — случайные величины. Определим взаимную информацию в а о в при условии у.

1. I(а : в | у) = Н(в | у) - Н(в | а,у).

2. I(а : в | У) = Е*I(а : в I У = се) • Рг[у = с*].

3. I(а : в | У) = Н(а | у) + Н(в | у) - Н(а,в | у).

4. I(а : в | У) = Н(а,у) + Н(в,у) - Н(а,в,у) - Н(у).

Утверждение 1.11. Все определения условной взаимной информации эквивалентны.

Утверждение 1.12 (цепное правило для взаимной информации). Имеют место следующие соотношения.

1. I((а,в) : у) = I(а : у) + I(в : У | а).

2. I((а,в) : У | 6) = I(а : у | 6) + I(в : У | а,6).

1.3 Коммуникационная сложность

В этом разделе излагаются самые базовые сведения по коммуникационной сложности, необходимые для дальнейшего повествования. Более подробно см. в [24; 30].

1.3.1 Классическая модель для двух игроков

Пусть X, У и Z — конечные множества, и пусть задана некоторая функция / : X х У ^ Z. Два игрока, будем называть их Алиса и Боб, решают коммуникационную задачу для функции /, если:

1. множества X, У, Z и функция / известны обоим игрокам,

2. Алиса знает некоторый х € X,

3. Боб знает некоторый у € У,

4. Алиса и Боб стремятся вычислить /(х,у).

Для решения этой коммуникационной задачи Алиса и Боб могут пересылать друг другу битовые сообщения. Задача считается решённой, если оба игрока знают /(х,у). Нас интересует минимальное количество битов, которое необходимо и достаточно переслать для вычисления /(х,у).

Определение 1.13. Коммуникационный протокол для функции / : X х У ^ Z — это корневое двоичное дерево с пометками. Каждая внутренняя вершина V помечена меткой «А» или «Б», а каждый лист помечен значением из множества Z. Кроме того, для каждой вершины, помеченной «А», определена функция дю : X ^ {0,1}, а для каждой вершины и с пометкой «Б» определена функция Ни : У ^ {0,1}. Каждая внутренняя вершина имеет двух потомков, ребро к первому потомку помечено 0, а ребро ко второму потомку помечено 1.

Общение по такому протоколу на конкретной паре входов (х,у) соответствует пути от корня к некоторому листу. Игроки начинают «находясь» в корне и дальше спускаются к листу. В каждой внутренней вершине V этого пути в зависимости от пометки либо Алиса (пометка «А»), либо Боб (пометка «Б») пересылает один бит, который равен, соответственно, ду(х) или (у). После

этого игроки «переходят» в одного из потомков вершины V по ребру, пометка которого совпадает с битом, переданным в вершине V. Когда игроки достигают листа, то их общение завершается. Результатом является пометка в этом листе.

Определение 1.14. Будем говорить, что коммуникационный протокол вычисляет функцию /, если для всех пар (х,у) Е X х У общение игроков завершается в листе с пометкой /(х,у).

Теперь можно дать формальное определение коммуникационной сложности функции /.

Определение 1.15. Коммуникационная сложность функции / определяется как наименьшая глубина протокола (максимальная рёберная длина пути от корня до листа), вычисляющего функцию /, и обозначается через СС(/).

Утверждение 1.16. Для любой / : {0,1}п х {0,1}п ^ {0,1}, СС(/) < п + 1.

Доказательство. Алиса посылает Бобу свой вход х за п сообщений, а затем Боб посылает Алисе значение /(х,у) за одно сообщение. □

Эти определения можно обобщить на более широкий класс задач, если предполагать, что вместо функции / : X х У ^ Z, Алиса и Боб решают коммуникационную задачу для отношения Я С (X х У) х Z:

1. множества X, У, Z и функция / известны обоим игрокам,

2. Алиса знает некоторый х Е X,

3. Боб знает некоторый у Е У,

4. Алиса и Боб стремятся найти такой г, что (х,у,г) Е Я, при этом гарантируется, что такой ^ существует.

В этих определения коммуникационную задачу для функции / можно рассматривать как коммуникационную задачу для отношения

) = {(х,У,1 (х,у)) | ж Е Х,у Е У}.

Определение коммуникационного протокола для отношения Я совпадает с определением коммуникационного протокола для функции.

Определение 1.17. Будем говорить, что коммуникационный протокол вычисляет отношение Я, если для всех пар (х,у) Е X х У общение игроков

завершается в листе с пометкой ^ € Z, такой что (х,у,г) € Я. Коммуникационная сложность отношения Я определяется как наименьшая глубина протокола, вычисляющего отношение Я, и обозначается СС(Д).

Замечание. В контексте коммуникационной сложности понятия «коммуникационная задача» и «коммуникационная игра» являются синонимами и могут использоваться вперемешку.

1.3.2 Нижние оценки

Рассмотрим коммуникационный протокол для некоторого отношения Р С X х У х Z. Для каждой вершины протокола V определим Яу С X х У — множество всех пар (х,у) € X х У, для которых общение проходит через вершину V.

Утверждение 1.18. Для любой вершины V множество Яу является комбинаторным прямоугольником, т.е. существуют такие Ху С X и Уи С У, что

Яу = Ху х Уу .

Доказательство. Утверждение верно для корня, т.к. множество всех входов игроков X х У является комбинаторным прямоугольником. Пусть для некоторой вершины V множество Яу является комбинаторным прямоугольником, т.е. выполняется Яу = Ху х Уу. Покажем, что утверждение выполняется и для её потомков. Если в этой вершине Алиса пересылает бит Ь, и игроки переходят в вершину и, то Яи = Хи х Уи, где Хи = {х € Ху | ду(х) = Ь}, а Уи = Уу. Аналогично, если в этой вершине Боб посылает бит Ь, и игроки переходят в вершину и, то Яи = Хи х Уи, где Хи = Ху, а Уи = {у € Уу | (у) = Ь}. □

Определение 1.19. Будем называть прямоугольник Я С X х У одноцветным для отношения Р, если существует такой ^ € Z, что для всех (х,у) € Я выполняется (х,у,г) € Р. Такой прямоугольник будем также называть ^-одноцветным.

Следствие 1.20. Листья коммуникационного протокола для отношения Р задают разбиение множества X х У на одноцветные прямоугольники.

Через х(Р) обозначим минимальное количество одноцветных для Р прямоугольников, покрывающих X х У.

Утверждение 1.21. CC(f) ^ log2 х(Р)•

Доказательство. Пусть L — это число листьев в оптимальном коммуникационном протоколе для Р. Тогда CC(f) ^ log2 L ^ logх(Р)• П

Метод полуаддитивной меры. Определим некоторую меру на подмножествах X х Y, которая является полуаддитивной, т.е. мера объединения двух множеств не превосходит суммы их мер. Пусть также для любого одноцветного прямоугольника R С X х Y выполняется ц,(R) ^ М для М > 0.

Утверждение 1.22. Верна следующая оценка

^ ^ х у)

И следовательно,

CC(P) > log2 ^^.

Метод трудного множества (fooling set). Это частный случай метода полуаддитивной меры, при котором фиксируется некоторое множество входов F С X х Y, а ^ определяется следующим образом:

р(А х В) = 1(А х В) П F

Если при этом множество F такое, что никакой одноцветный прямоугольник не содержит более одного элемента из F, то \(Р) ^ IP|, а следовательно CC(P) ^ log2 IF|.

1.3.3 Изучаемые функции

В коммуникационной сложности есть набор классических сложных функций, на примере которых можно продемонстрировать применение различных методов доказательства нижних оценок.

Определение 1.23. Равенство на битовых строках длины п — это функция EQn: {0,1}п х {0,1}п ^ {0,1}, заданная следующим соотношением:

Ух,у Е {0,1}п, ЕЦп(х,у) = 1 ^ ж = у.

Для функции равенства EQn можно показать, что не существует более эффективного протокола, чем наивный протокол, в котором Алиса посылает весь свой вход Бобу, а Боб вычисляет ответ и посылает его Алисе. Нижнюю оценку можно доказать, например, методом трудного множества.

Утверждение 1.24. CC(EQn) = п + 1.

Мы будем также использовать обобщение функции равенства, заданное на произвольном множестве.

Определение 1.25. Для любого конечного непустого множества S функция равенства на S — это функция EQ^ : S х S ^ {0,1}, такая что для любых a,b Е S выполняется EQ^(a,b) = 1 ^^ а = Ь.

Теорема 1.26. Для любого конечного непустого множества S

CC(EQ^) ^ log IS|.

Доказательство. Для любых а,Ь Е S, где а = Ь, 1-одноцветный прямоугольник, содержащий вход (а,а), не может содержать вход (b,b), иначе этот же прямоугольник содержал бы также входы (а,Ь) и (Ь,а), что противоречит его одноцветности. Таким образом диагональ множества S х S является трудным множеством размера IS|. □

Следующая функция задаёт внутреннее произведение на парах из {0,1}п. Так же, как и для функции равенства, для внутреннего произведения наивный протокол является оптимальным.

Определение 1.27. Внутреннее произведение на битовых строках длины п — это функция IPn: {0,1}п х {0,1}n ^ {0,1}, заданная следующим соотношением:

п

Ух,у Е {0,1}n, IPn(x,y) = хгУг mod 2.

i=1

Оценку для функции внутреннего произведения можно доказать при помощи метода полуаддитивной меры: взять меру Ц-(Д) = |Д|, воспользоваться фактом из леммы 3.24 и по-отдельности оценить количество листьев с пометками 0 и 1.

Утверждение 1.28. CC(IPn) = п + 1.

И ещё одна классическая сложная функция —это функция, являющаяся индикатором того, что два подмножества не пересекаются.

Определение 1.29. Дизъюнктность для битовых строк длины п — это функция Б18ЛП: {0,1}п х {0,1}п ^ {0,1}, заданная следующим соотношением:

Ух,у Е {0,1}п, Б18Лп(ж,у) = 1 ^^ У г Е [п],хгуг = 0.

Другими словами, можно сказать, что функция принимает пару характеристических функций, задающих подмножества [п], и равна 1 тогда и только тогда, когда эти подмножества дизъюнктны. Как и для двух предыдущих функций, для дизъюнктности не бывает протокола лучше, чем наивный. Оценку для функции дизъюнктности можно получить методом трудного множества воспользовавшись фактом из леммы 3.20.

Утверждение 1.30. СС(Б18ЛП) = п + 1.

В коммуникационной сложности эти три рассматриваемые функции позволяют разделить три различных модели: детерминированную, вероятностную и недетерминированную.

1.3.4 Недетерминированная коммуникационная сложность

Для результатов, изложенных в последней главе, нам потребуются оценки на недетерминированную сложность.

Определение 1.31. Будем говорить, что функция / : X х У ^ {0,1} имеет недетерминированный коммуникационный протокол сложности ¿, если существуют две функции А : X х {0,1}^ ^ {0,1} и В : У х {0,1}^ ^ {0,1}, такие что

- У(х,у) Е /-1(1) Е {0,1}^ : А(х^) = В(у,ы) = 1,

- У(х,у) Е /-1(0) У-ы Е {0,1}^ : А(х^) = 1 V В(у,ы) = 1. Недетерминированная коммуникационная сложность N(f) функции / — это минимальное (1, для которого существует недетерминированный коммуникационный протокол для / сложности 4.

В отличие от детерминированной коммуникационной сложности, определение недетерминированной коммуникационной сложности несимметрично, и следовательно, сложность функции и сложность её отрицания могут отличаться. Нас будет интересовать недетерминированная коммуникационная сложность функции неравенства.

Определение 1.32. Для любого конечного непустого множества S функция неравенства на S — это функция NEQ^ : S х S ^ {0,1}, такая что для любых a,b Е S выполняется NEQ^(a,b) = 1 — EQ^(а,Ь).

Теорема 1.33. Для любого конечного непустого множества S

N(NEQ^) ^ log log IS|.

Доказательство. Если IS| ^ 4, то утверждение тривиально. Пусть IS| > 4. Будем доказывать от противного. Предположим, что для некоторого S выполняется

N(NEQ^) = d < loglog IS| — 1.

Тогда следующий детерминированный коммуникационный протокол решает коммуникационную задачу для EQ^: Алиса посылает A(x,w) для всех возможных w Е {0,1}d, Боб в свою очередь отвечает 1 тогда и только тогда, когда для некоторого w Е {0,1}d выполняется A(x,w) = В(x,w) = 1. Сложность такого протокола равна

2d + 1 ^ 2loglog Is I-1 + 1 = + 1 < log IS I,

2

что противоречит теореме 1.26. □

Примечательное свойство недетерминированных коммуникационных протоколов заключается в том, что они не содержат никакой коммуникации между игроками. Для наших целей в некоторых случаях будет удобнее думать про альтернативное определение недетерминированных коммуникационных протоколов, которое неявно было сформулировано в классической книге Кушилевича и Нисана [24].

Определение 1.34. Будем говорить, что функция f : X х Y ^ {0,1} имеет приватный недетерминированный коммуникационный протокол сложности а, если существует функция f : (X х {0,1}*) х (Y х {0,1}*) ^ {0,1} (детерминированной) коммуникационной сложности не более d, такая что

- У(х,у) Е !-1(1) Эшх^у Е {0,1}* : /((ад), (у^у)) = 1,

- У(х,у) Е f-1(0) Уwx,wy Е {0,1}* : }((ад), (у^у)) = 0. Приватная недетерминированная коммуникационная сложность ) функции / — это минимальное (1, для которого существуют приватный недетерминированный коммуникационный протокол для / сложности d.

В оригинальном определении у игроков был доступ к общей (публичной) недетерминированной подсказке, что позволяло избежать коммуникации. В альтернативном определении у каждого игрока есть только своя приватная недетерминированная подсказка, поэтому игрокам приходится общаться. Докажем эквивалентность этих определений с точностью до аддитивной константы.

Список литературы диссертационного исследования кандидат наук Смаль Александр Владимирович, 2022 год

Список литературы

1. Андреев, А. Е. Об одном методе получения более чем квадратичных эффективных нижних оценок сложности п-схем // Вестн. Моск. ун-та. Сер. 1. Матем., мех. — 1987. — Вып. 1. — С. 70—73.

2. Верещагин, Н. К., Щепин, Е. В. Информация, кодирование и предсказание. — М.: ФМОП, МЦНМО, 2012. — С. 238.

3. Нечипорук, Э. И. Об одной булевской функции // Докл. АН СССР. — 1966. — Т. 169, вып. 4. — С. 765—766.

4. Субботовская, Б. А. О реализации линейных функций формулами в базисе V, &, - // Докл. АН СССР. — 1961. — Т. 136—3. — С. 553—555.

5. Храпченко, В. М. О сложности реализации линейной функции в классе П-схем // Матем. заметки. — 1971. — Т. 9, № 1. — С. 35—40.

6. Barak, B., Braverman, M., Chen, X., Rao, A. How to compress interactive communication // STOC 2010. — ACM, 2010. — С. 67—76. — URL: https: //doi.org/10.1145/1806689.1806701.

7. de Rezende, S. F., Meir, O, Nordstrom, J., Pitassi, T., Robere, R. KRW Composition Theorems via Lifting // FOCS 2020. — IEEE, 2020. — С. 43—49. — URL: https://doi.org/10.1109/F0CS46700.2020.00013.

8. Dementiev, Y., Ignatiev, A., Sidelnik, V., Smal, A., Ushakov, M. New Bounds on the Half-Duplex Communication Complexity // SOFSEM 2021. Т. 12607. — Springer, 2021. — С. 233—248. — (LNCS). — URL: https://doi.org/10.1007/ 978-3-030-67731-2%5C_17.

9. Dementiev, Y., Ignatiev, A., Sidelnik, V., Smal, A., Ushakov, M. New bounds on the half-duplex communication complexity // ECCC. — 2020. — Т. 27. — С. 117. — URL: https://eccc.weizmann.ac.il/report/2020/117.

10. Dinur, I., Meir, O. Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity // Comput. Complex. — 2018. — Т. 27, № 3. — С. 375—462. — URL: https://doi.org/10.1007/s00037-017-0159-x.

11. Edmonds, J., Impagliazzo, R., Rudich, S., Sgall, J. Communication complexity towards lower bounds on circuit depth // Computational Complexity. —

2001. — T. 10, № 3. — C. 210—246. — URL: https://doi.org/10.1007/s00037-001-8195-x.

12. Efremenko, K., Kol, G., Saxena, R. Interactive Coding Over the Noisy Broadcast Channel // ECCC. — 2017. — T. 24. — C. 93. — URL: https: //eccc.weizmann.ac.il/report/2017/093.

13. Gavinsky, D., Meir, O, Weinstein, O, Wigderson, A. Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture // STOC 2014. — ACM, 2014. — C. 213—222. — URL: https: //doi.org/10.1145/2591796.2591856.

14. Gavinsky, D., Meir, O, Weinstein, O, Wigderson, A. Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation // SIAM J. Comput. — 2017. — T. 46, № 1. — C. 114—131. — URL: https: //doi.org/10.1137/15M1018319.

15. Hastad, J. The Shrinkage Exponent of de Morgan Formulas is 2 // SIAM J. Comput. — 1998. — T. 27, № 1. — C. 48—64. — URL: https://doi.org/10. 1137/S0097539794261556.

16. Hastad, J., Wigderson, A. Composition of the Universal Relation // DIMACS 1990. T. 13. — DIMACS/AMS, 1990. — C. 119—134. — URL: http://dimacs. rutgers.edu/Volumes/Vol13.html.

17. Hoover, K., Impagliazzo, R., Mihajlin, I., Smal, A. Half-duplex communication complexity // ECCC. — 2018. — T. 25. — C. 89. — URL: https ://eccc. weizmann.ac.il/report/2018/089.

18. Hoover, K., Impagliazzo, R., Mihajlin, I., Smal, A. V. Half-Duplex Communication Complexity // ISAAC 2018. T. 123. — Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. — 10:1—10:12. — (LIPIcs). — URL: https://doi.org/10.4230/LIPIcs.ISAAC.2018.10.

19. Impagliazzo, R., Williams, R. Communication Complexity with Synchronized Clocks // CCC 2010. — IEEE Computer Society, 2010. — C. 259—269. — URL: https://doi.org/10.1109/CCC.2010.32.

20. Jukna, S. Boolean Function Complexity - Advances and Frontiers. T. 27. — Springer, 2012. — (Algorithms and combinatorics). — URL: https://doi.org/ 10.1007/978-3-642-24508-4.

21. Karchmer, M., Raz, R., Wigderson, A. Super-Logarithmic Depth Lower Bounds Via the Direct Sum in Communication Complexity // Computational Complexity. — 1995. — T. 5, № 3/4. — C. 191—204. — URL: https://doi.org/ 10.1007/BF01206317.

22. Karchmer, M, Wigderson, A. Monotone Circuits for Connectivity Require Super-logarithmic Depth // STOC 1988. — ACM, 1988. — C. 539—550. — URL: http://doi.acm.org/10.1145/62212.62265.

23. Koroth, S., Meir, O. Improved Composition Theorems for Functions and Relations // APPROX/RANDOM 2018. T. 116. — Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. — 48:1—48:18. — (LIPIcs). — URL: http:// drops.dagstuhl.de/opus/volltexte/2018/9452.

24. Kushilevitz, E., Nisan, N. Communication complexity. — Cambridge University Press, 1997.

25. Meir, O. Toward Better Depth Lower Bounds: Two Results on the Multiplexor Relation // Comput. Complex. — 2020. — T. 29, № 1. — C. 4. — URL: https: //doi.org/10.1007/s00037-020-00194-8.

26. Meir, O, Wigderson, A. Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds // ECCC. — 2017. — T. 24. — C. 149. — URL: https://eccc.weizmann.ac.il/report/2017/149.

27. Mihajlin, I., Smal, A. Toward Better Depth Lower Bounds: The XOR-KRW Conjecture // CCC 2021. T. 200. — Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. — 38:1—38:24. — (LIPIcs). — URL: https://drops.dagstuhl. de/opus/volltexte/2021/14312.

28. Paturi, R., Pudlak, P., Saks, M. E., Zane, F. An improved exponential-time algorithm for k-SAT //J. ACM. — 2005. — T. 52, № 3. — C. 337—364. — URL: http://doi.acm.org/10.1145/1066100.1066101.

29. Paturi, R., Pudlak, P., Zane, F. Satisfiability Coding Lemma // Chicago J. Theor. Comput. Sci. — 1999. — T. 1999. — URL: http://cjtcs.cs.uchicago.edu/ articles/1999/11/contents.html.

30. Rao, A., Yehudayoff, A. Communication Complexity: and Applications. — Cambridge University Press, 2020.

31. Razborov, A.A., Rudich, S. Natural proofs // Journal of Computer and System Sciences. — 1997. — T. 55, № 1. — C. 24—35.

32. Riordan, J., Shannon, C. E. The Number of Two-Terminal Series-Parallel Networks // Journal of Mathematics and Physics. — 1942. — T. 21, № 1—4. — C. 83—93. — URL: https://onlinelibrary.wiley.com/doi/abs/ 10.1002/ sapm194221183.

33. Smal, A., Talebanfard, N. Prediction from Partial Information and Hindsight, an Alternative Proof // ECCC. — 2017. — T. 24. — C. 191. — URL: https: //eccc.weizmann.ac.il/report/2017/191.

34. Smal, A. V., Talebanfard, N. Prediction from partial information and hindsight, an alternative proof // Inf. Process. Lett. — 2018. — T. 136. — C. 102—104. — URL: https://doi.org/10.1016/j.ipl.2018.04.011.

35. Tal, A. Shrinkage of De Morgan Formulae by Spectral Techniques // FOCS 2014. — IEEE Computer Society, 2014. — C. 551—560. — URL: https://doi. org/10.1109/F0CS.2014.65.

36. Viola, E. AC0 Unpredictability // ACM Trans. Comput. Theory. — 2021. — T. 13, № 1. — 5:1—5:8. — URL: https://doi.org/10.1145/3442362.

37. Yao, A. C.-C. Some Complexity Questions Related to Distributive Computing (Preliminary Report) // STOC 1979. — ACM, 1979. — C. 209—213. — URL: http://doi.acm.org/10.1145/800135.804414.