Меню Главная Случайная статья Настройки Коммуникационная сложность Материал из https://ru.wikipedia.org Коммуникационная сложность изучает количество коммуникации, необходимое для решения задачи, параметры которой распределены между двумя или более сторонами. Это понятие было введено Эндрю Яо в 1979 году[1], который исследовал следующую задачу для двух участников, традиционно называемых Алисой и Бобом. Алиса получает n-битную строку x, а Bob — n-битную строку y, и их цель состоит в том, чтобы один из них (например, Боб) вычислил определенную и известную обоим участникам функцию ${\displaystyle f(x,y)}$, при этом с наименьшим количеством коммуникации между ними. Конечно, они всегда могут вычислить ${\displaystyle f(x,y)}$ следующим образом: Алиса отправляет всю свою n-битную строку Бобу, который затем вычисляет функцию ${\displaystyle f(x,y)}$. Поэтому в данной постановке задачи интересно, для каких функций f существует способ вычислить ${\displaystyle f(x,y)}$ передав менее n битов. Важное отметить, что в данной задаче нас не интересует сложность вычислений, выполненных Алисой или Бобом, или размер используемой для этих вычислений памяти. Эта абстрактная проблема с двумя участниками (называемая коммуникационной сложностью с двумя участниками) и ее общая форма с большим количеством участников возникает в различных областях компьютерных наук: например, при проектировании больших интегральных схем требуется минимизировать используемую энергию, путём уменьшения количества электрических сигналов между различными компонентами во время распределенных вычислений. Коммуникационная сложность используется также при изучении структур данных и алгоритмов, при оптимизации компьютерных сетей, в теории вычислительной сложности и сложности доказательств и в других областях. Содержание 1 Формальное определение 1.1 Пример: функция EQ 1.2 Теорема: D(EQ) = n 2 Примечания 3 Литература Формальное определение Пусть изначально задана некоторая функция ${\displaystyle f:X\times Y\to Z}$, где в наиболее типичной постановке ${\displaystyle X=Y=\{0,1\}^{n},Z=\{0,1\}}$. Алиса получает элемент ${\displaystyle x\in X}$, Боб получает ${\displaystyle y\in Y}$. Обмениваясь друг с другом сообщениями по одному биту (используя некоторый заранее определённый протокол связи), Алиса и Боб хотят вычислить значение ${\displaystyle z=f(x,y)}$ так, чтобы в конце общения хотя бы один из них знал значение ${\displaystyle z}$. Коммуникационная сложность вычисления функции ${\displaystyle f}$, обозначается ${\displaystyle D(f)}$, определяется как минимальное количество бит коммуникации, которого достаточно для решения поставленной задачи в худшем случае (то есть этого количества битов должно быть достаточно для любой пары ${\displaystyle x,y}$). Опираясь на это определение удобно думать о функции f, как о функции, заданной матрицей Более формально, будем называть множество ${\displaystyle R\subseteq X\times Y}$ называется (комбинаторным) прямоугольником, если из того, ${\displaystyle (x_{1},y_{1})\in R}$ и ${\displaystyle (x_{2},y_{2})\in R}$, следует, что ${\displaystyle (x_{1},y_{2})\in R}$ и ${\displaystyle (x_{2},y_{1})\in R}$. Тогда каждая подматрица матрицы A ассоциируется с комбинаторными прямоугольником R, таким что ${\displaystyle R=M\times N}$, где ${\displaystyle M\subseteq X}$ и ${\displaystyle N\subseteq Y}$. Теперь рассмотрим ситуацию, когда между участниками уже передано k битов. Пусть эти первые k битов задаются строкой ${\displaystyle h\in \{0,1\}^{k}}$. Тогда можно определить множество пар входов ${\displaystyle T_{\mathrm {h} }\subseteq X\times Y}$, на которых первые k равны ${\displaystyle h}$ ${\displaystyle T_{\mathrm {h} }=\{(x,y):k}$-бит коммуникации на входах ${\displaystyle (x,y)}$ равен ${\displaystyle h\}}$ Тогда ${\displaystyle T_{\mathrm {h} }}$ является комбинаторным прямоугольником, то есть задаёт подматрицу матрицы A. Пример: функция EQ Пусть ${\displaystyle X=Y=\{0,1\}^{n},Z=\{0,1\}}$. Рассмотрим задачу, в которой Алиса и Боб хотят определить, даны ли им одинаковые строки, то есть они хотят проверить, что ${\displaystyle x=y}$. Несложно показать, что для решения этой задачи проверки равенства (EQ) потребуется передать n битов в худшем случае, если мы хотим быть научиться отвечать на этот вопрос точно для всех возможных пар x и y. Для случая ${\displaystyle n=3}$ строки 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 Как мы видим, функция ${\displaystyle EQ}$ равна 1 только в ячейках, где x равно y (то есть, на диагонали). Теорема: D(EQ) = n Доказательство. Предположим, что ${\displaystyle D(EQ)\leq n-1}$, то есть существует протокол, который решает задачу проверки равенства для всех пар битовых строк длины n, передавая при этом не более ${\displaystyle n-1}$ бита. Давайте для каждой возможной пары одинаковых строк ${\displaystyle (x,x)}$ (для них ${\displaystyle EQ(x,x)=1}$) выпишем в строчку все биты, которые пересылались в протоколе. Всего таких различных пар ${\displaystyle (x,x)}$ ровно ${\displaystyle 2^{n}}$, а различных битовых строк длины не более ${\displaystyle n-1}$ всего ${\displaystyle 2+4+\dotsb +2^{n-1}=2^{n}-2<2^{n}}$. По принципу Дирихле найдутся две пары ${\displaystyle (x,x)}$ и ${\displaystyle (x',x')}$, для которых получились одинаковые строки, то есть в протоколе пересылались одни и те же биты. Так как множество пар строк, для которых пересылались одинаковые биты, задаёт прямоугольник, то ${\displaystyle EQ(x,x')}$ и ${\displaystyle EQ(x',x)}$ тоже должны быть равны 1, что противоречит тому, что ${\displaystyle x\neq x'}$. Следовательно наше предположение неверно, а значит ${\displaystyle D(EQ)>n-1}$ Другими словами, если ${\displaystyle D(EQ)}$ меньше n, то мы должны уметь покрыть все единички матрицы EQ при помощи менее ${\displaystyle 2^{n}}$ одноцветных прямоугольников (все ячейки которых помечены единицами). Однако, в матрице EQ ровно ${\displaystyle 2^{n}}$ единичек, и никакие две не могут лежать в одном одноцветном прямоугольнике, так как тогда в этот прямоугольник неизбежно попадую ячейки помеченные нулями. Поэтому, такого покрытия не существует, а значит ${\displaystyle D(EQ)}$ как минимум n. Примечания Yao, A. C. (1979), Some Complexity Questions Related to Distributed Computing, Proc. of 11th STOC, 14: 209–213 Литература 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.