Коммуникационная сложность: различия между версиями
[непроверенная версия] | [непроверенная версия] |
Avsmal (обсуждение | вклад) определения матрицы функции и пример EQ Метка: редактор вики-текста 2017 |
Avsmal (обсуждение | вклад) Нет описания правки |
||
Строка 10: | Строка 10: | ||
''Коммуникационная сложность вычисления функции <math>f</math>'', обозначатся <math>D(f)</math>, определяется как минимальное количество бит коммуникации, которого достаточно для решения поставленной задачи в худшем случае (т.е. этого количества битов должно быть достаточно для любой пары <math>x,y</math>). |
''Коммуникационная сложность вычисления функции <math>f</math>'', обозначатся <math>D(f)</math>, определяется как минимальное количество бит коммуникации, которого достаточно для решения поставленной задачи в худшем случае (т.е. этого количества битов должно быть достаточно для любой пары <math>x,y</math>). |
||
Опираясь на это определение удобно думать о функции {{mvar|f}}, как о функции, заданной [[Матрица (математика)|матрицей]] {{mvar|A}}, в которой строки |
Опираясь на это определение удобно думать о функции {{mvar|f}}, как о функции, заданной [[Матрица (математика)|матрицей]] {{mvar|A}}, в которой строки индексированы элементами <math>x \in X</math>, а столбцы, соответственно, элементами <math>y \in Y</math>. В каждой ячейке этой матрицы, индексированной элементами {{mvar|x}} и {{mvar|y}}, записано соответствующее значение {{mvar|f}}, т.е. <math>A_{\mathrm{x,y}}=f(x,y)</math>. Алиса и Боб знают функцию {{mvar|f}}, а следовательно знают матрицу {{mvar|A}}. Далее, Алисе выдаётся номер строчки {{mvar|x}}, а Бобу -- номер столбца {{mvar|y}}, и их задача -- определить значение, записанное в соответствующей ячейке. Поэтому, если в какой-то момент один из игроков будет знать одновременно и номер столбца и номер строчки, то он будет знать и значение в соответствующей ячейке. В начале коммуникации каждый игрок ничего не знает про строчку другого игрока, поэтому с точки зрения Алисы ответом может быть любое значение в строчке с номером {{mvar|x}}, а с точки зрения Боба -- любое значение в столбце {{mvar|y}}. В процессе коммуникации с каждым переданным битом появляется новая информация, которая позволяет игрокам отсекать часть возможных ячеек. Например, если в какой-то момент Алиса передаёт бит {{mvar|b}}, то с точки зрения Боба все возможные к этому моменту входы Алисы делятся на два множества: те, для которых Алиса послала бы <math>b=0</math>, и те, для которых Алиса послала бы <math>b=1</math>. Зная значение бита {{mvar|b}} Боб отсекает часть возможных входов Алисы и таким образом сужает множество возможных с его точки зрения ячеек. При этом с точки зрения внешнего наблюдателя после каждого сообщения сужается либо множество возможных строк, либо множество возможных столбцов, и таким образом множество возможных ячеек сужается на некоторую [[Подматрица|подматрицу]] матрицы {{mvar|A}}. |
||
Более формально, будем называть множество <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|A}} ассоциируется с комбинаторными прямоугольником {{mvar|R}}, таким что <math>R = M \times N</math>, где <math>M \subseteq X</math> и <math>N \subseteq Y</math>. Теперь рассмотрим ситуацию, когда между участниками уже переданно {{mvar|k}} битов. Пусть эти первые {{mvar|k}} битов задаются строкой <math>h \in \{0,1\}^k</math>. Тогда можно определить множество пар входов <math>T_{\mathrm{h}} \subseteq X \times Y</math>, на которых первые {{mvar|k}} равны <math>h</math> |
Более формально, будем называть множество <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|A}} ассоциируется с комбинаторными прямоугольником {{mvar|R}}, таким что <math>R = M \times N</math>, где <math>M \subseteq X</math> и <math>N \subseteq Y</math>. Теперь рассмотрим ситуацию, когда между участниками уже переданно {{mvar|k}} битов. Пусть эти первые {{mvar|k}} битов задаются строкой <math>h \in \{0,1\}^k</math>. Тогда можно определить множество пар входов <math>T_{\mathrm{h}} \subseteq X \times Y</math>, на которых первые {{mvar|k}} равны <math>h</math> |
||
Строка 20: | Строка 20: | ||
=== Пример: функция EQ === |
=== Пример: функция EQ === |
||
Пусть <math>X=Y=\{0,1\}^n, Z=\{0,1\}</math>. Рассмотрим задачу, в которой Алиса и Боб хотят определить, даны ли им одинаковые строки, т.е. они хотят проверить, что <math>x=</math>. Несложно показать, что для решения этой задачи ''проверки равенства'' (EQ) потребуется передать {{mvar|n}} битов в худшем случае, если мы хотим быть научиться отвечать на этот вопрос точно для всех возможных пар {{mvar|x}} и {{mvar|y}}. |
Пусть <math>X=Y=\{0,1\}^n, Z=\{0,1\}</math>. Рассмотрим задачу, в которой Алиса и Боб хотят определить, даны ли им одинаковые строки, т.е. они хотят проверить, что <math>x=y</math>. Несложно показать, что для решения этой задачи ''проверки равенства'' ''(EQ)'' потребуется передать {{mvar|n}} битов в худшем случае, если мы хотим быть научиться отвечать на этот вопрос точно для всех возможных пар {{mvar|x}} и {{mvar|y}}. |
||
Для случая <math>n = 3</math> строки {{mvar|x}} и {{mvar|y}} состоят из трёх битов. Функция равенства в этом случае определяется следующей матрицей, в которой строки индексированы входами Алисы, а строчки -- входами Боба. |
Для случая <math>n = 3</math> строки {{mvar|x}} и {{mvar|y}} состоят из трёх битов. Функция равенства в этом случае определяется следующей матрицей, в которой строки индексированы входами Алисы, а строчки -- входами Боба. |
||
Версия от 10:14, 13 марта 2019
В теоретической информатике коммуникационная сложность изучает количество коммуникации, необходимое для решения задачи, параметры которой распределены между двумя или более сторонами. Это понятие было введено Эндрю Яо в 1979 году[1], который исследовал следующую задачу для двух участников, традиционно называемых Алисой и Бобом. Алиса получает n-битную строку x, а Bob — n-битную строку y, и их цель состоит в том, чтобы один из них (например, Боб) вычислил определенную и известную обоим участникам функцию , при этом с наименьшим количеством коммуникации между ними. Конечно, они всегда могут вычислить следующим образом: Алиса отправляет всю свою n-битную строку Бобу, который затем вычисляет функцию . Поэтому в данной постановке задачи интересно, для каких функций f существует способ вычислить передав менее n битов. Важное отметить, что в данной задаче нас не интересует сложность вычислений, выполненных Алисой или Бобом, или размер используемой для этих вычислений памяти.
Эта абстрактная проблема с двумя участниками (называемая коммуникационной сложностью с двумя участниками) и ее общая форма с большим количеством участников актуальна во многих контекстах: например, при проектировании схем больших интегральных схем требуется минимизировать используемую энергию, путем уменьшения количества электрических сигналов между различными компонентами во время распределенных вычислений. Коммуникационная сложность используется также при изучении структур данных и алгоритмов, при оптимизации компьютерных сетей, в теории вычислительной сложности и сложности доказательств и в других областях. Для обзора области см. Kushilevitz & Nisan (2006) .
Формальное определение
Пусть изначально задана некоторая функция , где в наиболее типичной постановке . Алиса получает элемент , Боб получает . Обмениваясь друг с другом сообщениями по одному биту (используя некоторый заранее определённый протокол связи ), Алиса и Боб хотят вычислить значение так, чтобы в конце общения хотя бы один из них знал значение .
Коммуникационная сложность вычисления функции , обозначатся , определяется как минимальное количество бит коммуникации, которого достаточно для решения поставленной задачи в худшем случае (т.е. этого количества битов должно быть достаточно для любой пары ).
Опираясь на это определение удобно думать о функции 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 |
Как мы видим, функция EQ равна 1 только в ячейках, где x равно y (т.е., на диагонали).
Примечания
- ↑ Yao, A. C. (1979), "Some Complexity Questions Related to Distributed Computing", Proc. of 11th STOC, 14: 209—213
Литература
- Kushilevitz, Eyal. Communication complexity / Eyal Kushilevitz, Noam Nisan. — 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.