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

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

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

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

Пусть изначально задана некоторая функция $f:X\times Y\to Z$, где в наиболее типичной постановке $X=Y=\{0,1\}^{n},Z=\{0,1\}$. Алиса получает элемент $x\in X$, Боб получает $y\in Y$. Обмениваясь друг с другом сообщениями по одному биту (используя некоторый заранее определённый протокол связи ), Алиса и Боб хотят вычислить значение $z=f(x,y)$ так, чтобы они оба знали значение $z$ в конце общения. Коммуникационная сложность вычисления функции $f$, обозначатся $D(f)$, определяется как минимальное количество бит коммуникации, которого достаточно для решения поставленной задачи в худшем случае (т.е. этого количества битов должно быть достаточно для любой пары $x,y$).