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

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

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

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

Пусть изначально задана некоторая функция , где в наиболее типичной постановке . Алиса получает элемент , Боб получает . Обмениваясь друг с другом сообщениями по одному биту (используя некоторый заранее определённый протокол связи ), Алиса и Боб хотят вычислить значение так, чтобы в конце общения хотя бы один из них знал значение .

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

Опираясь на это определение удобно думать о функции f , как о функции, заданной матрицей A , в которой строки индексированы элементами , а столбцы, соответственно, элементами . В каждой ячейке этой матрицы, индексированной элементами x и y , записано соответствующее значение f , то есть . Алиса и Боб знают функцию f , а следовательно знают матрицу A . Далее, Алисе выдаётся номер строчки x , а Бобу — номер столбца y , и их задача — определить значение, записанное в соответствующей ячейке. Поэтому, если в какой-то момент один из игроков будет знать одновременно и номер столбца и номер строчки, то он будет знать и значение в соответствующей ячейке. В начале коммуникации каждый игрок ничего не знает про номер другого игрока, поэтому с точки зрения Алисы ответом может быть любое значение в строчке с номером x , а с точки зрения Боба — любое значение в столбце y . В процессе коммуникации с каждым переданным битом появляется новая информация, которая позволяет игрокам отсекать часть возможных ячеек. Например, если в какой-то момент Алиса передаёт бит b , то с точки зрения Боба все возможные к этому моменту входы Алисы делятся на два множества: те, для которых Алиса послала бы , и те, для которых Алиса послала бы . Зная значение бита b Боб отсекает часть возможных входов Алисы и таким образом сужает множество возможных с его точки зрения ячеек. При этом с точки зрения внешнего наблюдателя после каждого сообщения сужается либо множество возможных строк, либо множество возможных столбцов, и таким образом множество возможных ячеек сужается на некоторую матрицы A .

Более формально, будем называть множество называется (комбинаторным) прямоугольником , если из того, и , следует, что и . Тогда каждая подматрица матрицы A ассоциируется с комбинаторными прямоугольником R , таким что , где и . Теперь рассмотрим ситуацию, когда между участниками уже передано k битов. Пусть эти первые k битов задаются строкой . Тогда можно определить множество пар входов , на которых первые k равны

-бит коммуникации на входах равен

Тогда является комбинаторным прямоугольником, то есть задаёт подматрицу матрицы A .

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

Пусть . Рассмотрим задачу, в которой Алиса и Боб хотят определить, даны ли им одинаковые строки, то есть они хотят проверить, что . Несложно показать, что для решения этой задачи проверки равенства (EQ) потребуется передать n битов в худшем случае, если мы хотим быть научиться отвечать на этот вопрос точно для всех возможных пар x и y .

Для случая строки 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

Как мы видим, функция равна 1 только в ячейках, где x равно y (то есть, на диагонали).

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

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

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

Примечания

  1. Yao, A. C. (1979), "Some Complexity Questions Related to Distributed Computing", Proc. of 11th STOC , 14 : 209—213

Литература

Источник —

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