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

Коммуникационная сложность изучает количество коммуникации, необходимое для решения задачи, параметры которой распределены между двумя или более сторонами. Это понятие было введено Эндрю Яо в 1979 году, который исследовал следующую задачу для двух участников, традиционно называемых Алисой и Бобом. Алиса получает n-битную строку x, а Bob — n-битную строку y, и их цель состоит в том, чтобы один из них (например, Боб) вычислил определенную и известную обоим участникам функцию $f(x,y)$, при этом с наименьшим количеством коммуникации между ними. Конечно, они всегда могут вычислить $f(x,y)$ следующим образом: Алиса отправляет всю свою n-битную строку Бобу, который затем вычисляет функцию $f(x,y)$. Поэтому в данной постановке задачи интересно, для каких функций f существует способ вычислить $f(x,y)$ передав менее n битов. Важное отметить, что в данной задаче нас не интересует сложность вычислений, выполненных Алисой или Бобом, или размер используемой для этих вычислений памяти.

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

Формальное определение

Пусть изначально задана некоторая функция $f:X\times Y\to Z$, где в наиболее типичной постановке $X=Y=\{0,1{\}}^n,Z=\{0,1\}$. Алиса получает элемент $x\in X$, Боб получает $y\in Y$. Обмениваясь друг с другом сообщениями по одному биту (используя некоторый заранее определённый протокол связи), Алиса и Боб хотят вычислить значение $z=f(x,y)$ так, чтобы в конце общения хотя бы один из них знал значение $z$.

Коммуникационная сложность вычисления функции $f$, обозначается $D(f)$, определяется как минимальное количество бит коммуникации, которого достаточно для решения поставленной задачи в худшем случае (то есть этого количества битов должно быть достаточно для любой пары $x,y$).

Опираясь на это определение удобно думать о функции Шаблон:Mvar, как о функции, заданной матрицей Шаблон:Mvar, в которой строки индексированы элементами $x\in X$, а столбцы, соответственно, элементами $y\in Y$. В каждой ячейке этой матрицы, индексированной элементами Шаблон:Mvar и Шаблон:Mvar, записано соответствующее значение Шаблон:Mvar, то есть $A_{\mathrm{x},\mathrm{y}}=f(x,y)$. Алиса и Боб знают функцию Шаблон:Mvar, а следовательно знают матрицу Шаблон:Mvar. Далее, Алисе выдаётся номер строчки Шаблон:Mvar, а Бобу — номер столбца Шаблон:Mvar, и их задача — определить значение, записанное в соответствующей ячейке. Поэтому, если в какой-то момент один из игроков будет знать одновременно и номер столбца и номер строчки, то он будет знать и значение в соответствующей ячейке. В начале коммуникации каждый игрок ничего не знает про номер другого игрока, поэтому с точки зрения Алисы ответом может быть любое значение в строчке с номером Шаблон:Mvar, а с точки зрения Боба — любое значение в столбце Шаблон:Mvar. В процессе коммуникации с каждым переданным битом появляется новая информация, которая позволяет игрокам отсекать часть возможных ячеек. Например, если в какой-то момент Алиса передаёт бит Шаблон:Mvar, то с точки зрения Боба все возможные к этому моменту входы Алисы делятся на два множества: те, для которых Алиса послала бы $b=0$, и те, для которых Алиса послала бы $b=1$. Зная значение бита Шаблон:Mvar Боб отсекает часть возможных входов Алисы и таким образом сужает множество возможных с его точки зрения ячеек. При этом с точки зрения внешнего наблюдателя после каждого сообщения сужается либо множество возможных строк, либо множество возможных столбцов, и таким образом множество возможных ячеек сужается на некоторую подматрицу матрицы Шаблон:Mvar.

Более формально, будем называть множество $R\subseteq X\times Y$ называется (комбинаторным) прямоугольником, если из того, $(x_1,y_1)\in R$ и $(x_2,y_2)\in R$, следует, что $(x_1,y_2)\in R$ и $(x_2,y_1)\in R$. Тогда каждая подматрица матрицы Шаблон:Mvar ассоциируется с комбинаторными прямоугольником Шаблон:Mvar, таким что $R=M\times N$, где $M\subseteq X$ и $N\subseteq Y$. Теперь рассмотрим ситуацию, когда между участниками уже передано Шаблон:Mvar битов. Пусть эти первые Шаблон:Mvar битов задаются строкой $h\in \{0,1{\}}^k$. Тогда можно определить множество пар входов $T_{\mathrm{h}}\subseteq X\times Y$, на которых первые Шаблон:Mvar равны $h$

$T_{\mathrm{h}}=\{(x,y):k$-бит коммуникации на входах $(x,y)$ равен $h\}$

Тогда $T_{\mathrm{h}}$ является комбинаторным прямоугольником, то есть задаёт подматрицу матрицы Шаблон:Mvar.

Пример: функция EQ

Пусть $X=Y=\{0,1{\}}^n,Z=\{0,1\}$. Рассмотрим задачу, в которой Алиса и Боб хотят определить, даны ли им одинаковые строки, то есть они хотят проверить, что $x=y$. Несложно показать, что для решения этой задачи проверки равенства (EQ) потребуется передать Шаблон:Mvar битов в худшем случае, если мы хотим быть научиться отвечать на этот вопрос точно для всех возможных пар Шаблон:Mvar и Шаблон:Mvar.

Для случая $n=3$ строки Шаблон:Mvar и Шаблон:Mvar состоят из трёх битов. Функция равенства в этом случае определяется следующей матрицей, в которой строки индексированы входами Алисы, а строчки — входами Боба.

EQ	000	001	010	011	100	101	110	111
000	1	0	0	0	0	0	0	0
001	0	1	0	0	0	0	0	0
010	0	0	1	0	0	0	0	0
011	0	0	0	1	0	0	0	0
100	0	0	0	0	1	0	0	0
101	0	0	0	0	0	1	0	0
110	0	0	0	0	0	0	1	0
111	0	0	0	0	0	0	0	1

Как мы видим, функция $EQ$ равна 1 только в ячейках, где Шаблон:Mvar равно Шаблон:Mvar (то есть, на диагонали).

Теорема: D(EQ) = n

Доказательство. Предположим, что $D(EQ)\le n-1$, то есть существует протокол, который решает задачу проверки равенства для всех пар битовых строк длины Шаблон:Mvar, передавая при этом не более $n-1$ бита. Давайте для каждой возможной пары одинаковых строк $(x,x)$ (для них $EQ(x,x)=1$) выпишем в строчку все биты, которые пересылались в протоколе. Всего таких различных пар $(x,x)$ ровно $2^n$, а различных битовых строк длины не более $n-1$ всего $2+4+\cdots +2^{n-1}=2^n-2<2^n$. По принципу Дирихле найдутся две пары $(x,x)$ и $(x^{\prime },x^{\prime })$, для которых получились одинаковые строки, то есть в протоколе пересылались одни и те же биты. Так как множество пар строк, для которых пересылались одинаковые биты, задаёт прямоугольник, то $EQ(x,x^{\prime })$ и $EQ(x^{\prime },x)$ тоже должны быть равны 1, что противоречит тому, что $x\ne x^{\prime }$. Следовательно наше предположение неверно, а значит $D(EQ)>n-1$

Другими словами, если $D(EQ)$ меньше Шаблон:Mvar, то мы должны уметь покрыть все единички матрицы EQ при помощи менее $2^n$ одноцветных прямоугольников (все ячейки которых помечены единицами). Однако, в матрице EQ ровно $2^n$ единичек, и никакие две не могут лежать в одном одноцветном прямоугольнике, так как тогда в этот прямоугольник неизбежно попадую ячейки помеченные нулями. Поэтому, такого покрытия не существует, а значит $D(EQ)$ как минимум Шаблон:Mvar.

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга