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

Сложность отправки информации в распределенном алгоритме

В теоретической информатике, сложность связи изучает объем связи, необходимый для решения проблемы, когда входные данные для проблемы распределяются между двумя или более сторонами. Изучение сложности связи было впервые введено Эндрю Яо в 1979 году при изучении проблемы вычислений, распределенных между несколькими машинами. Проблема обычно формулируется следующим образом: две стороны (традиционно называемые Алиса и Боб ) каждая получают (потенциально разные) $n\; \{\backslash \; displaystyle\; n\}$-бит строку $x\; \{\backslash \; displaystyle\; x\}$и $y\; \{\backslash \; displaystyle\; y\}$. Цель состоит в том, чтобы Алиса вычислила значение определенной функции, $f\; (x,\; y)\; \{\backslash \; displaystyle\; f\; (x,\; y)\}$, которая зависит от обоих параметров $x\; \{\backslash \; displaystyle\; x\}$и $y\; \{\backslash \; displaystyle\; y\}$с наименьшим объемом связи между ними.

Хотя Алиса и Боб всегда могут добиться успеха, если Боб отправит всю свою $n\; \{\backslash \; displaystyle\; n\}$-битную строку Алисе (которая затем вычисляет функцию $f\; \{\backslash \; displaystyle\; f\}$), идея состоит в том, чтобы найти умные способы вычисления $f\; \{\backslash \; displaystyle\; f\}$с меньшим, чем $n\; \{\backslash \; displaystyle\; n\}$битов связи. Обратите внимание, что, в отличие от теории вычислительной сложности, сложность связи не связана с объемом вычислений, выполняемых Алисой или Бобом, или размером используемой памяти., так как мы обычно ничего не предполагаем относительно вычислительной мощности Алисы или Боба.

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

• 1 Формальное определение
  • 1.1 Пример: $EQ\; \{\backslash \; displaystyle\; EQ\}$
  • 1.2 Теорема : $D\; (EQ)\; =\; n\; \{\backslash \; displaystyle\; D\; (EQ)\; =\; n\}$
• 2 Рандомизированная сложность связи
  • 2.1 Пример: EQ
  • 2.2 Пример: GH
  • 2.3 Общедоступные монеты против частных монет
• 3 Сложность квантовой связи
• 4 Недетерминированная сложность связи
• 5 Сложность связи с неограниченными ошибками
• 6 Открытые проблемы
• 7 Приложения
• 8 См. Также
• 9 Примечания
• 10 Ссылки

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

$D\; (f)\; =\; \{\backslash \; displaystyle\; D\; (f)\; =\}$минимальное количество битов, которыми обмениваются Алиса и Боб в худшем случае.

Как отмечалось выше, для любой функции $f:\; \{0,\; 1\}\; n\; \times \; \{0,\; 1\}\; n\; \to \; \{0,\; 1\}\; \{\backslash \; displaystyle\; f:\; \backslash \; \{0,1\; \backslash \}\; ^\; \{n\}\; \backslash \; times\; \backslash \; \{0,1\}\; \backslash \}\; ^\; \{n\}\; \backslash \; rightarrow\; \backslash \; \{0,1\; \backslash \}\}$, мы имеем $D\; (f)\; \le \; n\; \{\backslash \; displaystyle\; D\; (f)\; \backslash \; leq\; n\}$. Используя приведенное выше определение, полезно рассматривать функцию $f\; \{\backslash \; displaystyle\; f\}$как matrix $A\; \{\backslash \; displaystyle\; A\}$(называемой входной матрицей или матрицей связи), где строки индексируются $x\; \in \; X\; \{\backslash \; displaystyle\; x\; \backslash \; in\; X\}$, а столбцы - $y\; \in \; Y\; \{\backslash \; displaystyle\; y\; \backslash \; в\; Y\}$. Элементы матрицы: $A\; x,\; y\; =\; f\; (x,\; y)\; \{\backslash \; displaystyle\; A\_\; \{x,\; y\}\; =\; f\; (x,\; y)\}$. Первоначально и Алиса, и Боб имеют копию всей матрицы $A\; \{\backslash \; displaystyle\; A\}$(предполагается, что функция $f\; \{\backslash \; displaystyle\; f\}$известна обоим стороны). Тогда проблема вычисления значения функции может быть перефразирована как «обнуление» соответствующей записи матрицы. Эта проблема может быть решена, если Алиса или Боб знают и $x\; \{\backslash \; displaystyle\; x\}$, и $y\; \{\backslash \; displaystyle\; y\}$. В начале коммуникации количество вариантов значения функции на входах равно размеру матрицы, то есть $2\; 2\; n\; \{\backslash \; displaystyle\; 2\; ^\; \{2n\}\}$. Затем, когда каждая сторона немного общается с другой, количество вариантов ответа уменьшается, так как это исключает набор строк / столбцов, что приводит к подматрице из $A\; \{\backslash \; displaystyle\; A\; \}$.

Более формально, набор $R\; \subseteq \; X\; \times \; Y\; \{\backslash \; displaystyle\; R\; \backslash \; substeq\; X\; \backslash \; times\; Y\}$называется (комбинаторным) прямоугольником, если всякий раз, когда $(x\; 1,\; y\; 1)\; \in \; R\; \{\backslash \; displaystyle\; (x\_\; \{1\},\; y\_\; \{1\})\; \backslash \; in\; R\}$и $(x\; 2,\; y\; 2)\; \in \; R\; \{\backslash \; displaystyle\; (x\_\; \{2\}),\; y\_\; \{2\})\; \backslash \; in\; R\}$, тогда $(x\; 1,\; y\; 2)\; \in \; R\; \{\backslash \; displaystyle\; (x\_\; \{1\},\; y\_\; \{2\})\; \backslash \; in\; R\}$. Эквивалентно, $R\; \{\backslash \; displaystyle\; R\}$является комбинаторным прямоугольником, если его можно выразить как $R\; =\; M\; \times \; N\; \{\backslash \; displaystyle\; R\; =\; M\; \backslash \; times\; N\}$для некоторых $M\; \subseteq \; X\; \{\backslash \; displaystyle\; M\; \backslash \; substeq\; X\}$и $N\; \subseteq \; Y\; \{\backslash \; displaystyle\; N\; \backslash \; substeq\; Y\}$. Рассмотрим случай, когда биты $k\; \{\backslash \; displaystyle\; k\}$уже обмениваются между сторонами. Теперь для конкретного $h\; \in \; \{0,\; 1\}\; k\; \{\backslash \; displaystyle\; h\; \backslash \; in\; \backslash \; \{0,1\; \backslash \}\; ^\; \{k\}\}$, давайте определим матрицу

$T\; h\; =\; \{(x,\; y):\; k\; -биты,\; которыми\; обмениваются\; при\; вводе\; (x,\; y),\; равно\; h\}\; \{\backslash \; displaystyle\; T\_\; \{h\}\; =\; \backslash \; \{(x,\; y):\; \{\backslash \; text\; \{the\}\}\; k\; \{\backslash \; text\; \{-биты,\; которыми\; обмениваются\; при\; вводе\}\}\; (x,\; y)\; \{\backslash \; text\; \{is\}\}\; h\; \backslash \}\}$

Тогда, $T\; h\; \subseteq \; X\; \times \; Y\; \{\backslash \; displaystyle\; T\_\; \{h\}\; \backslash \; substeq\; X\; \backslash \; раз\; Y\}$, и нетрудно показать, что $T\; h\; \{\backslash \; displaystyle\; T\_\; \{h\}\}$является комбинаторным прямоугольником в $A\; \{\backslash \; displaystyle\; A\; \}$.

Пример: $EQ\; \{\backslash \; displaystyle\; EQ\}$

Мы рассматриваем случай, когда Алиса и Боб пытаются определить, равны ли их входные строки. Формально определите функцию равенства, обозначенную $EQ:\; \{0,\; 1\}\; n\; \times \; \{0,\; 1\}\; n\; \to \; \{0,\; 1\}\; \{\backslash \; displaystyle\; EQ:\; \backslash \; \{0,1\; \backslash \}\; ^\; \{n\}\; \backslash \; times\; \backslash \; \{0,1\; \backslash \}\; ^\; \{n\}\; \backslash \; rightarrow\; \backslash \; \{0,1\; \backslash \}\}$, на $EQ\; (x,\; y)\; =\; 1\; \{\backslash \; displaystyle\; EQ\; (x,\; y)\; =\; 1\}$iff $x\; =\; y\; \{\backslash \; displaystyle\; x\; =\; y\}$. Как показано ниже, любой детерминированный протокол связи, решающий $E\; Q\; \{\backslash \; displaystyle\; EQ\}$, в худшем случае требует $n\; \{\backslash \; displaystyle\; n\}$битов связи. В качестве примера для разминки рассмотрим простой случай $x,\; y\; \in \; \{0,\; 1\}\; 3\; \{\backslash \; displaystyle\; x,\; y\; \backslash \; in\; \backslash \; \{0,1\; \backslash \}\; ^\; \{3\}\}$. Функция равенства в этом случае может быть представлена ​​следующей матрицей. Строки представляют все возможности $x\; \{\backslash \; displaystyle\; x\}$, столбцы - $y\; \{\backslash \; displaystyle\; 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\; \{\backslash \; displaystyle\; x\}$равно $y\; \{\backslash \; displaystyle\; y\}$(т. е. по диагонали). Также довольно легко увидеть, как передача одного бита делит ваши возможности пополам. Если вы знаете, что первый бит $y\; \{\backslash \; displaystyle\; y\}$равен 1, вам нужно учитывать только половину столбцов (где $y\; \{\backslash \; displaystyle\; y\}$может равняться 100, 101, 110 или 111).

Теорема: $D\; (E\; Q)\; =\; n\; \{\backslash \; displaystyle\; D\; (EQ)\; =\; n\}$

Доказательство. Предположим, что $D\; (E\; Q)\; \le \; n\; -\; 1\; \{\backslash \; displaystyle\; D\; (EQ)\; \backslash \; leq\; n-1\}$. Это означает, что существует $x\; \ne \; x\; \prime \; \{\backslash \; displaystyle\; x\; \backslash \; neq\; x\; \text{'}\}$такое, что $(x,\; x)\; \{\backslash \; displaystyle\; (x,\; x)\}$и $(x\; \prime ,\; x\; \prime )\; \{\backslash \; displaystyle\; (x\; \text{'},\; x\text{'})\}$, которые имеют одинаковую транскрипцию связи $h\; \{\backslash \; displaystyle\; h\}$. Поскольку эта расшифровка определяет прямоугольник, $f\; (x,\; x\; \prime )\; \{\backslash \; displaystyle\; f\; (x,\; x\; \text{'})\}$также должен быть 1. По определению $x\; \ne \; x\; \prime \; \{\backslash \; displaystyle\; x\; \backslash \; neq\; x\; \text{'}\}$, и мы знаем, что равенство верно только для $(a,\; b)\; \{\backslash \; displaystyle\; (a,\; b)\}$когда $a\; знак\; равно\; б\; \{\backslash \; Displaystyle\; а\; =\; Ь\}$. Получили противоречие.

Этот метод доказательства нижних границ детерминированной связи называется методом ошибочного набора.

Рандомизированная сложность связи

В приведенном выше определении нас интересует количество битов, которые должны детерминированно передаваться между двумя сторонами. Если обеим сторонам предоставляется доступ к генератору случайных чисел, могут ли они определить значение $f\; \{\backslash \; displaystyle\; f\}$при гораздо меньшем объеме обмена информацией? Яо в своей основополагающей статье отвечает на этот вопрос, определяя рандомизированную сложность коммуникации.

Случайный протокол $R\; \{\backslash \; displaystyle\; R\}$для функции $f\; \{\backslash \; displaystyle\; f\}$имеет двустороннюю ошибку.

$Pr\; [R\; (x,\; y)\; =\; 0]>2\; 3,\; если\; f\; (x,\; y)\; =\; 0\; \{\backslash \; displaystyle\; \backslash \; Pr\; [R\; (x,\; y)\; =\; 0]>\{\backslash \; frac\; \{2\}\; \{\; 3\}\},\; \{\backslash \; textrm\; \{if\}\}\; \backslash ,\; f\; (x,\; y)\; =\; 0\}$

$Pr\; [R\; (x,\; y)\; =\; 1]>2\; 3,\; если\; f\; (x,\; y)\; =\; 1\; \{\backslash \; displaystyle\; \backslash \; Pr\; [R\; (x,\; y)\; =\; 1]>\{\backslash \; frac\; \{2\}\; \{3\}\; \},\; \{\backslash \; textrm\; \{if\}\}\; \backslash ,\; f\; (x,\; y)\; =\; 1\}$

A рандомизированный протокол - это детерминированный протокол, который использует дополнительную случайную строку в дополнение к обычному вводу. Для этого есть две модели: общедоступная строка - это случайная строка, которая известна обеим сторонам заранее, а частная строка генерируется одной стороной и должна быть передана другой стороне. Теорема, представленная ниже, показывает, что любой протокол общедоступной строки может быть смоделирован протоколом частной строки, который использует O (log n) дополнительных битов по сравнению с исходным.

Обратите внимание, что в приведенных выше вероятностных неравенствах результат протокола зависит только от случайной строки; обе строки x и y остаются фиксированными. Другими словами, если R (x, y) дает g (x, y, r) при использовании случайной строки r, то g (x, y, r) = f (x, y) по крайней мере для 2/3 всех варианты для строки r.

Рандомизированная сложность просто определяется как количество битов, которыми обмениваются в таком протоколе.

Обратите внимание, что также можно определить рандомизированный протокол с односторонней ошибкой, и сложность определяется аналогично.

Пример: EQ

Возвращаясь к предыдущему примеру EQ, если уверенность не требуется, Алиса и Боб могут проверить равенство, используя только $O\; (log\; \; n)\; \{\backslash \; displaystyle\; O\; (\backslash \; log\; n)\}$сообщений. Рассмотрим следующий протокол: предположим, что Алиса и Боб оба имеют доступ к одной и той же случайной строке $z\; \in \; \{0,\; 1\}\; n\; \{\backslash \; displaystyle\; z\; \backslash \; in\; \backslash \; \{0,1\; \backslash \}\; ^\; \{n\}\}$. Алиса вычисляет $z\; \cdot \; x\; \{\backslash \; displaystyle\; z\; \backslash \; cdot\; x\}$и отправляет этот бит (назовите его b) Бобу. ($(\cdot )\; \{\backslash \; displaystyle\; (\backslash \; cdot)\}$- это скалярное произведение в GF (2).) Затем Боб сравнивает b с $Z\; \cdot \; Y\; \{\backslash \; Displaystyle\; Z\; \backslash \; cdot\; y\}$. Если они совпадают, Боб соглашается, говоря, что x равно y. В противном случае он отвергает.

Очевидно, если $x\; =\; y\; \{\backslash \; displaystyle\; x\; =\; y\}$, то $z\; \cdot \; x\; =\; z\; \cdot \; y\; \{\backslash \; displaystyle\; z\; \backslash \; cdot\; x\; =\; z\; \backslash \; cdot\; y\}$, поэтому $P\; robz\; [A\; ccept]\; =\; 1\; \{\backslash \; displaystyle\; Prob\_\; \{z\}\; [Accept]\; =\; 1\}$. Если x не равно y, все еще возможно, что $z\; \cdot \; x\; =\; z\; \cdot \; y\; \{\backslash \; displaystyle\; z\; \backslash \; cdot\; x\; =\; z\; \backslash \; cdot\; y\}$, что даст Бобу неправильный ответ. Как это произошло?

Если x и y не равны, они должны различаться в некоторых местах:

$\{x\; =\; c\; 1\; c\; 2\dots \; p\dots \; p\; \prime \dots \; xny\; =\; c\; 1\; c\; 2\dots \; q\dots \; q\; \prime \dots \; ynz\; знак\; равно\; z\; 1\; z\; 2\dots \; zi\dots \; zj\dots \; zn\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{cases\}\; x\; =\; c\_\; \{1\}\; c\_\; \{2\}\; \backslash \; ldots\; p\; \backslash \; ldots\; p\; \text{'}\backslash \; ldots\; x\_\; \{n\}\; \backslash \backslash \; y\; =\; c\_\; \{1\; \}\; c\_\; \{2\}\; \backslash \; ldots\; q\; \backslash \; ldots\; q\; \text{'}\backslash \; ldots\; y\_\; \{n\}\; \backslash \backslash \; z\; =\; z\_\; \{1\}\; z\_\; \{2\}\; \backslash \; ldots\; z\_\; \{i\}\; \backslash \; ldots\; z\_\; \{j\}\; \backslash \; ldots\; z\_\; \{n\}\; \backslash \; end\; \{case\}\}\}$

Если x и y совпадают, $zi\; \ast \; xi\; =\; zi\; \ast \; ci\; =\; zi\; \ast \; yi\; \{\backslash \; displaystyle\; z\_\; \{i\}\; *\; x\_\; \{i\}\; =\; z\_\; \{i\}\; *\; c\_\; \{i\}\; =\; z\_\; \{i\}\; *\; y\_\; \{i\}\}$, поэтому эти термины одинаково влияют на скалярные произведения. Мы можем спокойно игнорировать эти термины и смотреть только на то, где различаются x и y. Кроме того, мы можем поменять местами биты $xi\; \{\backslash \; displaystyle\; x\_\; \{i\}\}$и $yi\; \{\backslash \; displaystyle\; y\_\; \{i\}\}$без изменения того, скалярные произведения равны. Это означает, что мы можем поменять местами биты так, чтобы x содержал только нули, а y содержал только единицы:

$\{x\; \prime \; =\; 00\dots \; 0\; y\; \prime \; =\; 11\dots \; 1\; z\; \prime \; =\; z\; 1\; z\; 2\dots \; zn\; \prime \; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{case\}\; x\; \text{'}=\; 00\; \backslash \; ldots\; 0\; \backslash \backslash \; y\text{'}\; =\; 11\; \backslash \; ldots\; 1\; \backslash \backslash \; z\; \text{'}=\; z\_\; \{1\}\; z\_\; \{2\}\; \backslash \; ldots\; z\_\; \{n\text{'}\}\; \backslash \; end\; \{ases\}\}\}$

Примечание что $z\; \prime \; \cdot \; x\; \prime \; =\; 0\; \{\backslash \; displaystyle\; z\; \text{'}\backslash \; cdot\; x\text{'}\; =\; 0\}$и $z\; \prime \; \cdot \; y\; \prime \; =\; \Sigma \; izi\; \prime \; \{\backslash \; displaystyle\; z\; \text{'}\backslash \; cdot\; y\; \text{'}=\; \backslash \; Sigma\; \_\; \{i\}\; z\text{'}\; \_\; \{i\}\}$. Теперь возникает вопрос: для некоторой случайной строки $z\; \prime \; \{\backslash \; displaystyle\; z\; \text{'}\}$, какова вероятность того, что $\Sigma \; izi\; \prime \; =\; 0\; \{\backslash \; displaystyle\; \backslash \; Sigma\; \_\; \{i\}\; z\; \text{'}\_\; \{i\}\; =\; 0\}$? Поскольку каждый $zi\; \prime \; \{\backslash \; displaystyle\; z\; \text{'}\_\; \{i\}\}$с одинаковой вероятностью равен 0 или 1, эта вероятность составляет всего $1/2\; \{\backslash \; displaystyle\; 1/2\}$. Таким образом, когда x не равно y, $P\; r\; o\; b\; z\; [A\; c\; c\; e\; p\; t]\; =\; 1/2\; \{\backslash \; displaystyle\; Prob\_\; \{z\}\; [Accept]\; =\; 1/2\}$. Алгоритм можно повторять много раз, чтобы повысить его точность. Это соответствует требованиям к рандомизированному алгоритму связи.

Это показывает, что если Алиса и Боб совместно используют случайную строку длины n, они могут послать один бит друг другу для вычисления $EQ\; (x,\; y)\; \{\backslash \; displaystyle\; EQ\; (x,\; y)\}$. В следующем разделе показано, что Алиса и Боб могут обмениваться только $O\; (log\; \; n)\; \{\backslash \; displaystyle\; O\; (\backslash \; log\; n)\}$битами, которые так же хороши, как и случайная строка. длины n. Как только это будет показано, следует, что EQ может быть вычислен в сообщениях $O\; (log\; \; n)\; \{\backslash \; displaystyle\; O\; (\backslash \; log\; n)\}$.

Пример: GH

В качестве еще одного примера рандомизированной сложности связи мы обратимся к примеру, известному как проблема разрыва-Хэмминга (сокращенно GH). Формально Алиса и Боб оба поддерживают двоичные сообщения, $x,\; y\; \in \; \{-\; 1,\; +\; 1\}\; n\; \{\backslash \; displaystyle\; x,\; y\; \backslash \; in\; \backslash \; \{-\; 1,\; +\; 1\; \backslash \}\; ^\; \{n\}\}$и хотел бы определить, очень ли похожи строки или нет. В частности, они хотели бы найти протокол связи, требующий передачи как можно меньшего количества битов для вычисления следующей частичной булевой функции,

$GH\; n\; (x,\; y):\; =\; \{-\; 1\; ⟨x,\; y⟩\; \le \; -\; п\; +\; 1\; ⟨х,\; у⟩\; \ge \; п.\; \{\backslash \; displaystyle\; \{\backslash \; text\; \{GH\}\}\; \_\; \{n\}\; (x,\; y):\; =\; \{\backslash \; begin\; \{case\}\; -1\; \backslash \; langle\; x,\; y\; \backslash \; rangle\; \backslash \; leq\; -\; \{\backslash \; sqrt\; \{n\}\}\; \backslash \backslash \; +\; 1\; \backslash \; langle\; x,\; y\; \backslash \; rangle\; \backslash \; geq\; \{\backslash \; sqrt\; \{n\}\}.\; \backslash \; end\; \{cases\}\}\}$

Очевидно, они должны передавать все свои биты, если протокол должен быть детерминированным (это потому, что если есть детерминированное строгое подмножество индексов, которые Алиса и Боб передают друг другу, а затем представьте себе пару строк, которые в этом наборе не совпадают в $n\; -\; 1\; \{\backslash \; displaystyle\; \{\backslash \; sqrt\; \{n\}\}\; -\; 1\}$позиций. Если другое разногласие возникает в любой позиции, о которой не сообщается, это влияет на результат $GH\; n\; (x,\; y)\; \{\backslash \; displaystyle\; \{\backslash \; text\; \{GH\}\}\; \_\; \{n\}\; (x,\; y)\}$и, следовательно, приведет к неправильной процедуре.

Тогда возникает естественный вопрос, разрешено ли нам ошибаться $1/3\; \{\backslash \; displaystyle\; 1/3\}$времени (по случайным экземплярам $x,\; y\; \{\backslash \; displaystyle\; x,\; y\}$нарисовано равномерно случайным образом из $\{-\; 1,\; +\; 1\; \}\; n\; \{\backslash \; displaystyle\; \backslash \; \{-\; 1,\; +\; 1\; \backslash \}\; ^\; \{n\}\}$), тогда мы можем уйти с протоколом с меньшим количеством бит? Оказывается, что ответ несколько неожиданно отрицательный из-за результата Чакрабарти и Регева в 2012 году: они показывают, что для случайных экземпляров любая процедура, которая является правильной, по крайней мере $2/3\; \{\backslash \; displaystyle\; 2/3\}$времени должно передавать $\Omega \; (n)\; \{\backslash \; displaystyle\; \backslash \; Omega\; (n)\}$бит связи, то есть практически все из них.

Публичные монеты против частных монет

Легче создавать случайные протоколы, когда обе стороны имеют доступ к одной и той же случайной строке (протокол разделяемой строки). Эти протоколы по-прежнему можно использовать, даже если обе стороны не используют случайную строку (протокол частной строки) с небольшими затратами на связь. Любой протокол случайных строк с разделяемой строкой, использующий любое количество случайных строк, может быть смоделирован протоколом частных строк, который использует дополнительные O (log n) бит.

Интуитивно мы можем найти некоторый набор строк, в котором достаточно случайности для запуска случайного протокола с небольшим увеличением ошибки. Этот набор можно совместно использовать заранее, и вместо того, чтобы рисовать случайную строку, Алисе и Бобу нужно только согласовать, какую строку выбрать из общего набора. Этот набор достаточно мал, чтобы можно было эффективно сообщить о выборе. Далее следует формальное доказательство.

Рассмотрим некоторый случайный протокол P с максимальной частотой ошибок 0,1. Пусть $R\; \{\backslash \; displaystyle\; R\}$будет $100\; n\; \{\backslash \; displaystyle\; 100n\}$строк длиной n, пронумерованных $r\; 1,\; r\; 2,\dots ,\; r\; 100\; n\; \{\backslash \; displaystyle\; r\_\; \{1\},\; r\_\; \{2\},\; \backslash \; dots,\; r\_\; \{100n\}\}$. Учитывая такой $R\; \{\backslash \; displaystyle\; R\}$, определите новый протокол $PR\; \prime \; \{\backslash \; displaystyle\; P\; \text{'}\_\; \{R\}\}$, который случайным образом выбирает некоторые $ri\; \{\backslash \; displaystyle\; r\_\; \{i\}\}$, а затем запускает P, используя $ri\; \{\backslash \; displaystyle\; r\_\; \{i\}\}$в качестве общей случайной строки. Требуется O (log 100n) = O (log n) битов, чтобы сообщить о выборе $ri\; \{\backslash \; displaystyle\; r\_\; \{i\}\}$.

. Определим $p\; (x,\; y)\; \{\backslash \; displaystyle\; p\; (x,\; y)\}$и $p\; R\; \prime \; (x,\; y)\; \{\backslash \; displaystyle\; p\; \text{'}\_\; \{R\}\; (x,\; y)\}$как вероятности того, что $P\; \{\backslash \; displaystyle\; P\}$и $PR\; \prime \; \{\backslash \; displaystyle\; P\; \text{'}\_\; \{R\}\}$вычисляет правильное значение для входа $(x,\; y)\; \{\backslash \; displaystyle\; (x,\; y)\}$.

Для фиксированного $(x,\; y)\; \{\backslash \; displaystyle\; (x,\; y)\}$мы можем использовать неравенство Хёффдинга, чтобы получить следующее уравнение:

Таким образом, когда у нас нет $(x,\; y)\; \{\backslash \; displaystyle\; (x,\; y)\}$фиксировано:

Последнее равенство выше сохраняется, потому что существует $2\; 2\; n\; \{\backslash \; displaystyle\; 2\; ^\; \{2n\}\}$разных пар $(x,\; y)\; \{\backslash \; displaystyle\; (x,\; y)\}$. Поскольку вероятность не равна 1, существует $R\; 0\; \{\backslash \; displaystyle\; R\_\; \{0\}\}$, так что для всех $(x,\; y)\; \{\backslash \; displaystyle\; (x,\; y)\; \}$:

Поскольку $P\; \{\backslash \; displaystyle\; P\}$имеет вероятность ошибки не более 0,1, $PR\; 0\; \prime \; \{\backslash \; displaystyle\; P\; \text{'}\_\; \{R\_\; \{0\}\}\}$может иметь вероятность ошибки не более 0,2.

Сложность квантовой коммуникации пытается количественно оценить сокращение коммуникации, возможное за счет использования квантовых эффектов во время распределенных вычислений.

Было предложено по крайней мере три квантовых обобщения сложности коммуникации; для обзора см. предлагаемый текст Г. Брассара.

Первая - это модель кубитовой связи, где стороны могут использовать квантовую связь вместо классической связи, например, обменивая фотонами через оптическое волокно.

Во второй модели связь по-прежнему осуществляется с помощью классических битов, но сторонам разрешено манипулировать неограниченным количеством квантовых запутанных состояний в рамках своих протоколов. Измеряя свои запутанные состояния, стороны могут сэкономить на классической коммуникации во время распределенных вычислений.

Третья модель включает доступ к ранее совместно используемой запутанности в дополнение к обмену данными с кубитами и является наименее изученной из трех квантовых моделей.

При недетерминированной сложности связи Алиса и Боб имеют доступ к оракулу. После получения слова оракула стороны связываются, чтобы вывести $f\; (x,\; y)\; \{\backslash \; displaystyle\; f\; (x,\; y)\}$. Таким образом, недетерминированная коммуникационная сложность является максимальной по всем парам $(x,\; y)\; \{\backslash \; displaystyle\; (x,\; y)\}$по сумме количества битов, которыми обмениваются, и длины кодирования слова оракула..

С другой стороны, это равносильно покрытию всех 1-элементов 0/1-матрицы комбинаторными 1-прямоугольниками (т. Е. Несмежными невыпуклыми подматрицами, все элементы которых равны единице (см. Кушилевица и Нисан или Дицфельбингер и др.)). Недетерминированная коммуникационная сложность - это двоичный логарифм числа прямоугольников, покрывающих матрицу: минимальное количество комбинаторных 1-прямоугольников, необходимых для покрытия всех 1-элементов матрицы, без покрытия каких-либо 0-элементов.

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

В настройке неограниченных ошибок Алиса и Боб имеют доступ к частной монете и своим собственным входам $(\; х,\; у)\; \{\backslash \; Displaystyle\; (х,\; у)\}$. В этом случае Алиса преуспевает, если она ответит правильным значением $f\; (x,\; y)\; \{\backslash \; displaystyle\; f\; (x,\; y)\}$с вероятностью, строго большей 1/2. Другими словами, если ответы Алисы имеют ненулевую корреляцию с истинным значением $f\; (x,\; y)\; \{\backslash \; displaystyle\; f\; (x,\; y)\}$, то протокол считается действительным..

Обратите внимание, что требование, чтобы монета была частной, очень важно. В частности, если количество общедоступных битов, совместно используемых Алисой и Бобом, не учитывается при расчете сложности связи, легко утверждать, что вычисление любой функции имеет $O\; (1)\; \{\backslash \; displaystyle\; O\; (1)\}$коммуникационная сложность. С другой стороны, обе модели эквивалентны, если количество общедоступных битов, используемых Алисой и Бобом, засчитывается против общего обмена данными по протоколу.

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

Форстер был первым, кто доказал явные нижние границы для этого класса, показывая, что для вычисления внутреннего произведения $⟨x,\; y⟩\; \{\backslash \; displaystyle\; \backslash \; langle\; x,\; y\; \backslash \; rangle\}$требуется как минимум $\Omega \; (n)\; \{\backslash \; displaystyle\; \backslash \; Omega\; (n)\}$битов коммуникации, хотя более ранний результат Алона, Франкла и Рёдля доказал, что сложность коммуникации почти для всех булевых функций $е:\; \{0,\; 1\}\; n\; \times \; \{0,\; 1\}\; n\; \to \; \{0,\; 1\}\; \{\backslash \; displaystyle\; f:\; \backslash \; \{0,1\; \backslash \}\; ^\; \{n\}\; \backslash \; times\; \backslash \; \{0,1\; \backslash \}\; ^\; \{n\}\; \backslash \; to\; \backslash \; \{0,1\; \backslash \}\}$равно $\Omega \; (n)\; \{\backslash \; displaystyle\; \backslash \; Omega\; (n)\}$.

с учетом ввода 0 или 1 матрица $M\; е\; =\; [е\; (x,\; y)]\; x,\; y\; \in \; \{0,\; 1\}\; n\; \{\backslash \; displaystyle\; M\_\; \{f\}\; =\; [f\; (x,\; y)]\; \_\; \{x,\; y\; \backslash \; in\; \backslash \; \{0,1\; \backslash \}\; ^\; \{n\}\}\}$, минимальное количество битов, которыми обмениваются для вычисления $f\; \{\backslash \; displaystyle\; f\}$детерминированно в худшем случае, $D\; (f)\; \{\backslash \; displaystyle\; D\; (f)\}$, как известно, ограничено снизу логарифмом ранга матрицы $M\; f\; \{\backslash \; Displaystyle\; M\_\; \{f\}\}$. Гипотеза логарифмического ранга предполагает, что коммуникационная сложность, $D\; (f)\; \{\backslash \; displaystyle\; D\; (f)\}$, ограничена сверху постоянной степенью логарифма ранга $М\; е\; \{\backslash \; Displaystyle\; M\_\; \{f\}\}$. Поскольку D (f) ограничено сверху и снизу многочленами логарифмического ранга $(M\; f)\; \{\backslash \; displaystyle\; (M\_\; \{f\})\}$, можно сказать, что D (f) полиномиально связано для регистрации ранга $(M\; f)\; \{\backslash \; displaystyle\; (M\_\; \{f\})\}$. Поскольку ранг матрицы является полиномиальным вычислимым по размеру матрицы, такая верхняя граница позволит аппроксимировать коммуникационную сложность матрицы за полиномиальное время. Обратите внимание, однако, что размер самой матрицы экспоненциально зависит от размера входных данных.

Для рандомизированного протокола количество битов, которыми обмениваются в худшем случае, R (f), предположительно полиномиально связано со следующей формулой:

$log\; \; min\; (rank\; (M\; f\; \text{'})\; :\; M\; f\; \prime \; \in \; R\; 2\; n\; \times \; 2\; n,\; (M\; f\; -\; M\; f\; \prime )\; \infty \; \le \; 1/3).\; \{\backslash \; displaystyle\; \backslash \; log\; \backslash \; min\; (\{\backslash \; textrm\; \{rank\}\}\; (M\; \text{'}\_\; \{f\}):\; M\text{'}\; \_\; \{f\}\; \backslash \; in\; \backslash \; mathbb\; \{R\}\; ^\; \{2\; ^\; \{n\}\; \backslash \; times\; 2\; ^\; \{n\; \}\},\; (M\_\; \{f\}\; -M\; \text{'}\_\; \{f\})\; \_\; \{\backslash \; infty\}\; \backslash \; leq\; 1/3).\}$

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

Нижние границы сложности связи могут использоваться для доказательства нижних границ в сложности дерева решений, схем СБИС, структурах данных, алгоритмы потоковой передачи, пространственно-временные компромиссы для машин Тьюринга и др.

• проблема Гэпа-Хэмминга

• Кушилевиц, Эял; Нисан, Ноам (2006). Коммуникационная сложность. Кембридж: Издательство Кембриджского университета. ISBN 978-0-521-02983-4. OCLC 70764786. CS1 maint: ref = harv (link )
• Brassard, G. Сложность квантовой коммуникации: обзор. https: // arxiv.org/abs/quant-ph/0101005
• Дицфельбингер, М., Дж. Хромкович, Дж., и Г. Шнитгер, «Сравнение двух методов определения нижней границы сложности связи », Theoret. Comput. Sci. 168, 1996. 39-51.
• Raz, Ran. "Circuit and Communication Complexity." In Computational Complexity Theory. Стивен Рудич и Ави Вигдерсон, редакторы Института Американского математического общества Advanced Study, 2004. 129–137.
• AC Yao, «Некоторые вопросы сложности, связанные с распределенными вычислениями», Proc. Of 11th STOC, pp. 209–213, 1979. 14
• I. Ньюман, Частные и обычные случайные биты в сложности связи, Information Processing Letters 39, 1991, стр. 67–71.