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

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

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

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

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

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

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

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

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

Тогда [math]\displaystyle{ T_{\mathrm{h}} }[/math] является комбинаторным прямоугольником, то есть задаёт подматрицу матрицы A.

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

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

Для случая [math]\displaystyle{ n = 3 }[/math] строки x и y состоят из трёх битов. Функция равенства в этом случае определяется следующей матрицей, в которой строки индексированы входами Алисы, а строчки — входами Боба.

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

Как мы видим, функция [math]\displaystyle{ EQ }[/math] равна 1 только в ячейках, где x равно y (то есть, на диагонали).

Теорема: [math]\displaystyle{ D(EQ) = n }[/math]

Доказательство. Предположим, что [math]\displaystyle{ D(EQ) \leq n-1 }[/math], то есть существует протокол, который решает задачу проверки равенства для всех пар битовых строк длины n, передавая при этом не более [math]\displaystyle{ n-1 }[/math] бита. Давайте для каждой возможной пары одинаковых строк [math]\displaystyle{ (x, x) }[/math] (для них [math]\displaystyle{ EQ(x, x)=1 }[/math]) выпишем в строчку все биты, которые пересылались в протоколе. Всего таких различных пар [math]\displaystyle{ (x,x) }[/math] ровно [math]\displaystyle{ 2^n }[/math], а различных битовых строк длины не более [math]\displaystyle{ n-1 }[/math] всего [math]\displaystyle{ 2 + 4 + \dotsb + 2^{n-1} = 2^n - 2 \lt 2^n }[/math]. По принципу Дирихле найдутся две пары [math]\displaystyle{ (x, x) }[/math] и [math]\displaystyle{ (x', x') }[/math], для которых получились одинаковые строки, то есть в протоколе пересылались одни и те же биты. Так как множество пар строк, для которых пересылались одинаковые биты, задаёт прямоугольник, то [math]\displaystyle{ EQ(x, x') }[/math] и [math]\displaystyle{ EQ(x', x) }[/math] тоже должны быть равны 1, что противоречит тому, что [math]\displaystyle{ x \neq x' }[/math]. Следовательно наше предположение неверно, а значит [math]\displaystyle{ D(EQ) \gt n-1 }[/math]

Другими словами, если [math]\displaystyle{ D(EQ) }[/math] меньше n, то мы должны уметь покрыть все единички матрицы EQ при помощи менее [math]\displaystyle{ 2^n }[/math] одноцветных прямоугольников (все ячейки которых помечены единицами). Однако, в матрице EQ ровно [math]\displaystyle{ 2^n }[/math] единичек, и никакие две не могут лежать в одном одноцветном прямоугольнике, так как тогда в этот прямоугольник неизбежно попадую ячейки помеченные нулями. Поэтому, такого покрытия не существует, а значит [math]\displaystyle{ D(EQ) }[/math] как минимум n.

Литература

• Kushilevitz, Eyal; Nisan, Noam Communication complexity (неопр.). — Cambridge: Cambridge University Press, 2006. — ISBN 978-0-521-02983-4.
• Разборов А.А. Коммуникационная сложность. — МЦНМО, 2012. — 24 с. — ISBN 978-5-4439-0202-9.
• Верещагин Н.К., Щепин Е.В. Информация, кодирование и предсказание. — М.: ФМОП, МЦНМО, 2012. — 238 с. — ISBN 978-5-94057-920-5.