Русская Википедия:Коммуникационная сложность
В теоретической информатике коммуникационная сложность изучает количество коммуникации, необходимое для решения задачи, параметры которой распределены между двумя или более сторонами. Это понятие было введено Эндрю Яо в 1979 году[1], который исследовал следующую задачу для двух участников, традиционно называемых Алисой и Бобом. Алиса получает n-битную строку x, а Bob — n-битную строку y, и их цель состоит в том, чтобы один из них (например, Боб) вычислил определенную и известную обоим участникам функцию <math>f(x,y)</math>, при этом с наименьшим количеством коммуникации между ними. Конечно, они всегда могут вычислить <math>f(x,y)</math> следующим образом: Алиса отправляет всю свою n-битную строку Бобу, который затем вычисляет функцию <math>f(x,y)</math>. Поэтому в данной постановке задачи интересно, для каких функций f существует способ вычислить <math>f(x,y)</math> передав менее n битов. Важное отметить, что в данной задаче нас не интересует сложность вычислений, выполненных Алисой или Бобом, или размер используемой для этих вычислений памяти.
Эта абстрактная проблема с двумя участниками (называемая коммуникационной сложностью с двумя участниками) и ее общая форма с большим количеством участников возникает в различных областях компьютерных наук: например, при проектировании больших интегральных схем требуется минимизировать используемую энергию, путём уменьшения количества электрических сигналов между различными компонентами во время распределенных вычислений. Коммуникационная сложность используется также при изучении структур данных и алгоритмов, при оптимизации компьютерных сетей, в теории вычислительной сложности и сложности доказательств и в других областях.
Формальное определение
Пусть изначально задана некоторая функция <math>f: X\times Y \to Z</math>, где в наиболее типичной постановке <math>X=Y=\{0,1\}^n, Z=\{0,1\}</math>. Алиса получает элемент <math>x\in X</math>, Боб получает <math>y\in Y</math>. Обмениваясь друг с другом сообщениями по одному биту (используя некоторый заранее определённый протокол связи), Алиса и Боб хотят вычислить значение <math>z = f(x,y)</math> так, чтобы в конце общения хотя бы один из них знал значение <math>z</math>.
Коммуникационная сложность вычисления функции <math>f</math>, обозначается <math>D(f)</math>, определяется как минимальное количество бит коммуникации, которого достаточно для решения поставленной задачи в худшем случае (то есть этого количества битов должно быть достаточно для любой пары <math>x,y</math>).
Опираясь на это определение удобно думать о функции Шаблон:Mvar, как о функции, заданной матрицей Шаблон:Mvar, в которой строки индексированы элементами <math>x \in X</math>, а столбцы, соответственно, элементами <math>y \in Y</math>. В каждой ячейке этой матрицы, индексированной элементами Шаблон:Mvar и Шаблон:Mvar, записано соответствующее значение Шаблон:Mvar, то есть <math>A_{\mathrm{x,y}}=f(x,y)</math>. Алиса и Боб знают функцию Шаблон:Mvar, а следовательно знают матрицу Шаблон:Mvar. Далее, Алисе выдаётся номер строчки Шаблон:Mvar, а Бобу — номер столбца Шаблон:Mvar, и их задача — определить значение, записанное в соответствующей ячейке. Поэтому, если в какой-то момент один из игроков будет знать одновременно и номер столбца и номер строчки, то он будет знать и значение в соответствующей ячейке. В начале коммуникации каждый игрок ничего не знает про номер другого игрока, поэтому с точки зрения Алисы ответом может быть любое значение в строчке с номером Шаблон:Mvar, а с точки зрения Боба — любое значение в столбце Шаблон:Mvar. В процессе коммуникации с каждым переданным битом появляется новая информация, которая позволяет игрокам отсекать часть возможных ячеек. Например, если в какой-то момент Алиса передаёт бит Шаблон:Mvar, то с точки зрения Боба все возможные к этому моменту входы Алисы делятся на два множества: те, для которых Алиса послала бы <math>b=0</math>, и те, для которых Алиса послала бы <math>b=1</math>. Зная значение бита Шаблон:Mvar Боб отсекает часть возможных входов Алисы и таким образом сужает множество возможных с его точки зрения ячеек. При этом с точки зрения внешнего наблюдателя после каждого сообщения сужается либо множество возможных строк, либо множество возможных столбцов, и таким образом множество возможных ячеек сужается на некоторую подматрицу матрицы Шаблон:Mvar.
Более формально, будем называть множество <math>R \subseteq X \times Y</math> называется (комбинаторным) прямоугольником, если из того, <math>(x_1,y_1) \in R</math> и <math>(x_2,y_2) \in R</math>, следует, что <math>(x_1,y_2) \in R</math> и <math>(x_2,y_1) \in R</math>. Тогда каждая подматрица матрицы Шаблон:Mvar ассоциируется с комбинаторными прямоугольником Шаблон:Mvar, таким что <math>R = M \times N</math>, где <math>M \subseteq X</math> и <math>N \subseteq Y</math>. Теперь рассмотрим ситуацию, когда между участниками уже передано Шаблон:Mvar битов. Пусть эти первые Шаблон:Mvar битов задаются строкой <math>h \in \{0,1\}^k</math>. Тогда можно определить множество пар входов <math>T_{\mathrm{h}} \subseteq X \times Y</math>, на которых первые Шаблон:Mvar равны <math>h</math>
- <math>T_{\mathrm{h}} = \{ (x, y) : k</math>-бит коммуникации на входах <math>(x , y)</math> равен <math>h\}</math>
Тогда <math>T_{\mathrm{h}}</math> является комбинаторным прямоугольником, то есть задаёт подматрицу матрицы Шаблон:Mvar.
Пример: функция EQ
Пусть <math>X=Y=\{0,1\}^n, Z=\{0,1\}</math>. Рассмотрим задачу, в которой Алиса и Боб хотят определить, даны ли им одинаковые строки, то есть они хотят проверить, что <math>x=y</math>. Несложно показать, что для решения этой задачи проверки равенства (EQ) потребуется передать Шаблон:Mvar битов в худшем случае, если мы хотим быть научиться отвечать на этот вопрос точно для всех возможных пар Шаблон:Mvar и Шаблон:Mvar.
Для случая <math>n = 3</math> строки Шаблон: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 |
Как мы видим, функция <math>EQ</math> равна 1 только в ячейках, где Шаблон:Mvar равно Шаблон:Mvar (то есть, на диагонали).
Теорема: D(EQ) = n
Доказательство. Предположим, что <math>D(EQ) \leq n-1</math>, то есть существует протокол, который решает задачу проверки равенства для всех пар битовых строк длины Шаблон:Mvar, передавая при этом не более <math>n-1</math> бита. Давайте для каждой возможной пары одинаковых строк <math>(x, x)</math> (для них <math>EQ(x, x)=1</math>) выпишем в строчку все биты, которые пересылались в протоколе. Всего таких различных пар <math>(x,x)</math> ровно <math>2^n</math>, а различных битовых строк длины не более <math>n-1</math> всего <math>2 + 4 + \dotsb + 2^{n-1} = 2^n - 2 < 2^n</math>. По принципу Дирихле найдутся две пары <math>(x, x)</math> и <math>(x', x')</math>, для которых получились одинаковые строки, то есть в протоколе пересылались одни и те же биты. Так как множество пар строк, для которых пересылались одинаковые биты, задаёт прямоугольник, то <math>EQ(x, x')</math> и <math>EQ(x', x)</math> тоже должны быть равны 1, что противоречит тому, что <math>x \neq x'</math>. Следовательно наше предположение неверно, а значит <math>D(EQ) > n-1</math>
Другими словами, если <math>D(EQ)</math> меньше Шаблон:Mvar, то мы должны уметь покрыть все единички матрицы EQ при помощи менее <math>2^n</math> одноцветных прямоугольников (все ячейки которых помечены единицами). Однако, в матрице EQ ровно <math>2^n</math> единичек, и никакие две не могут лежать в одном одноцветном прямоугольнике, так как тогда в этот прямоугольник неизбежно попадую ячейки помеченные нулями. Поэтому, такого покрытия не существует, а значит <math>D(EQ)</math> как минимум Шаблон:Mvar.
Примечания
Литература
