Коммуникационная сложность: различия между версиями

м
Улучшение
м (Улучшение)
В [[Теоретическая информатика|теоретической информатике]] '''коммуникационная сложность''' изучает количество коммуникации, необходимое для решения задачи, параметры которой [[Распределённые вычисления|распределены]] между двумя или более сторонами. Это понятие было введено [[Яо, Эндрю|Эндрю Яо]] в 1979 году<ref name="yao1979">{{Citation|last=Yao|first=A. C.|title=Some Complexity Questions Related to Distributed Computing|journal=Proc. of 11th STOC|volume=14|pages=209–213|year=1979}}</ref>, который исследовал следующую задачу для двух участников, традиционно называемых [[Алиса и Боб|Алисой и Бобом]]. Алиса получает ''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 битов. Важное отметить, что в данной задаче нас не интересует [[Вычислительная сложность|сложность вычислений,]] выполненных Алисой или Бобом, или размер используемой для этих вычислений памяти.
 
Эта абстрактная проблема с двумя участниками (называемая коммуникационной сложностью с двумя участниками) и ее общая форма с большим количеством участников актуальнавозникает вов многихразличных контекстахобластях компьютерных наук: например, при проектировании схем [[Интегральная схема|больших интегральных схем]] требуется минимизировать используемую энергию, путем уменьшения количества электрических сигналов между различными компонентами во время распределенных вычислений. Коммуникационная сложность используется также при изучении структур данных и алгоритмов, при оптимизации компьютерных сетей, в теории вычислительной сложности и сложности доказательств и в других областях. Для обзора области см. {{Harvtxt|Kushilevitz|Nisan|2006}} .
 
== Формальное определение ==
Пусть изначально задана некоторая функция <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|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>T_{\mathrm{h}} = \{ (x, y) : k</math>-бит коммуникации на входах <math>(x , y)</math> равен <math>h\}</math>