Введение 3
1. Обзорный раздел по предметной области 5
1.1. Используемые определения 5
1.2. Используемые факты 6
2. Верхняя оценка на функцию дизъюнктности 8
3. Другие результаты 12
3.1. Функция рекурсивного голосования 12
3.2. Функция четности 13
Заключение 15
Список литературы 16
В классической модели коммуникационной сложности, предложенной Яо [6], два игрока — Алиса и Боб хотят вычислить значение f (х,у) для некоторой булевой функции f. Изначально Алиса имеет только битовую строчку х, а Боб — у. Они могут общаться, посылая друг другу биты, по одному за раунд. В конце коммуникации игроки должны знать результат f (х, у). Например Алиса может отправить все биты своей строки Бобу, после чего он может посчитать значение функции f (х, у) и отправить результат Алисе. Однако обычно существуют более эффективные с точки зрения количества отправленных друг другу битов коммуникационные протоколы.
Важным ограничением классической модели является то, что за один раунд только один игрок может посылать бит. В статье [2] рассматривается расширение модели, суть которого заключается в том, что игрокам позволяется посылать биты одновременно. Такой канал связи называется полудуплексным. Пример такого канала — общение по рации. Особенность этой модели заключается в том, что в один момент времени игрок может либо только говорить, либо только слушать. То есть если собеседники попытаются говорить одновременно, то оба ничего не услышат.
В такой модели каждый раунд каждый игрок совершает одно из следующих действий: отправить 1, отправить 0 или принимать. Если один игрок посылает, а другой принимает, то такой раунд ничем не отличается от классического, его называют нормальным. Если оба игрока посылают биты, то эти биты теряются, будем называть такие раунды потерянными. Если оба игрока принимают, то такие раунды будем называть тихими. В зависимости от канала связи в тихом раунде могут возникать разные ситуации, в связи с этим определены три модели.
• Модель с нулем: оба игрока в тихом раунде получают 0. В этом случае они не могут отличить ноль, полученный от другого игрока, от нуля, полученного в результате тихого раунда. Сложность функции f в этой модели обозначается как Dgd(f).
• Модель с тишиной: в тихом раунде игроки получают специальный символ тишины, то есть, в отличие от случая с тишиной, игроки различают тихие раунды. Сложность функции f в этой модели обозначается как D^d(f).
• Модель с противником: в тихом раунде каждый игрок получает либо 0, либо 1. Можно представить что есть некий противник, который пытается помешать коммуникации, выбирая какой бит Алиса и Боб услышат в тихом раунде. В такой модели игроки не могут отличить тихий раунд от нормального. Сложность функции f в этой модели обозначается как Ddd(f).
Цель данной работы — исследовать описанные выше модели полудуплексной коммуникационной сложности, сравнить их с классической моделью и между собой. Мы получим верхнюю оценку в модели с нулём для функции дизъюнктности, классическая коммуникационная сложность которой уже известна. Это поможет нам понять то, что модели с нулем и противником не равны.
На примере функции дизъюнктности мы убедились, что модель с противником и модель с нулём отличаются. Результаты данной работы вошли в публикацию [3]. Оценка на полудуплексную коммуникационную сложность функции дизъюнктности не является точной: во всех трёх полудуплексных моделях между верхней и нижней оценкой есть зазор, а в модели с противником нет верхней оценки лучше тривиальной. Будет интересно получить любое улучшение какой-либо из представленных в таблице 5 оценок.
Также известно [3], что классическая и полудуплексная сложности ведут себя по-разному. Например, для функций равенства и внутреннего произведения сложности в классическом случае совпадают, а в полудуплексном — отличаются. На данный момент нельзя утверждать, что полудуплексные коммуникационные сложности функций внутреннего произведения и дизъюнктности отличаются, но очень похоже, что это действительно так. Мы знаем, что Dq^(IP^) > п/ log2(2/(3 — д/5)) « 0.72п и Dq^(DISJn) < 0.75п + о(п). Зазор между этими оценками небольшой, поэтому вполне возможно, что их получится разъединить.
