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

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

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

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

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

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

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

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

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

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

Потом, ${ displaystyle T_ {h} substeq X times Y}$, и нетрудно показать, что ${ displaystyle T_ {h}}$ комбинаторный прямоугольник в ${ displaystyle A}$.

Пример: ${ displaystyle EQ}$

Мы рассматриваем случай, когда Алиса и Боб пытаются определить, равны ли их входные строки. Формально определим Равенство функция, обозначенная ${ Displaystyle EQ: {0,1 } ^ {n} times {0,1 } ^ {n} rightarrow {0,1 }}$, от ${ displaystyle EQ (x, y) = 1}$ если только ${ displaystyle x = y}$. Как показано ниже, решение любого детерминированного протокола связи ${ displaystyle EQ}$ требует ${ displaystyle n}$ биты связи в худшем случае. В качестве примера разминки рассмотрим простой случай ${ Displaystyle х, у в {0,1 } ^ {3}}$. Функция равенства в этом случае может быть представлена ​​следующей матрицей. Строки представляют все возможности ${ displaystyle x}$, столбцы ${ displaystyle y}$.

Как видите, функция принимает значение 1 только тогда, когда ${ displaystyle x}$ равно ${ displaystyle y}$ (т.е. по диагонали). Также довольно легко увидеть, как передача одного бита делит ваши возможности пополам. Если вы знаете, что первая часть ${ displaystyle y}$ равно 1, вам нужно рассмотреть только половину столбцов (где ${ displaystyle y}$ может равняться 100, 101, 110 или 111).

Теорема: ${ Displaystyle D (EQ) = п}$

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

Этот метод доказательства нижних границ детерминированной коммуникации называется дурацкий набор техника.^[2]

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

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

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

${ displaystyle Pr [R (x, y) = 0]> { frac {2} {3}}, { textrm {if}} , f (x, y) = 0}$

${ displaystyle Pr [R (x, y) = 1]> { frac {2} {3}}, { textrm {if}} , f (x, y) = 1}$

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

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

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

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

Пример: EQ

Возвращаясь к предыдущему примеру Эквалайзер, если уверенность не требуется, Алиса и Боб могут проверить равенство, используя только ${ Displaystyle О ( журнал п)}$ Сообщения. Рассмотрим следующий протокол: предположим, что Алиса и Боб оба имеют доступ к одной и той же случайной строке. ${ Displaystyle г в {0,1 } ^ {п}}$. Алиса вычисляет ${ Displaystyle г cdot х}$ и отправляет этот бит (назовите его б) Бобу. (The ${ Displaystyle ( cdot)}$ это скалярное произведение в GF (2).) Затем Боб сравнивает б к ${ Displaystyle г cdot у}$. Если они совпадают, Боб соглашается, говоря Икс равно у. В противном случае он отвергает.

Очевидно, что если ${ displaystyle x = y}$, тогда ${ Displaystyle Z CDOT Икс = Z CDOT Y}$, так ${ displaystyle Prob_ {z} [Принять] = 1}$. Если Икс не равно у, все еще возможно, что ${ Displaystyle Z CDOT Икс = Z CDOT Y}$, что даст Бобу неправильный ответ. Как это произошло?

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

${ displaystyle { begin {case} x = c_ {1} c_ {2} ldots p ldots p ' ldots x_ {n} y = c_ {1} c_ {2} ldots q ldots q ' ldots y_ {n} z = z_ {1} z_ {2} ldots z_ {i} ldots z_ {j} ldots z_ {n} end {case}}}$

куда Икс и у дать согласие, ${ displaystyle z_ {i} * x_ {i} = z_ {i} * c_ {i} = z_ {i} * y_ {i}}$ поэтому эти термины одинаково влияют на скалярные произведения. Мы можем спокойно игнорировать эти термины и смотреть только на то, где Икс и у отличаются. Кроме того, мы можем поменять местами биты ${ displaystyle x_ {i}}$ и ${ displaystyle y_ {i}}$ без изменения, равны ли скалярные произведения. Это означает, что мы можем поменять местами биты, чтобы Икс содержит только нули и у содержит только единицы:

${ displaystyle { begin {cases} x '= 00 ldots 0 y' = 11 ldots 1 z '= z_ {1} z_ {2} ldots z_ {n'} end {case} }}$

Обратите внимание, что ${ displaystyle z ' cdot x' = 0}$ и ${ displaystyle z ' cdot y' = Sigma _ {i} z '_ {я}}$. Теперь возникает вопрос: для некоторой случайной строки ${ displaystyle z '}$, какова вероятность того, что ${ Displaystyle Sigma _ {я} г '_ {я} = 0}$? Поскольку каждый ${ displaystyle z '_ {я}}$ с равной вероятностью будет 0 или 1, эта вероятность просто ${ displaystyle 1/2}$. Таким образом, когда Икс не равно у,${ displaystyle Prob_ {z} [Принять] = 1/2}$. Алгоритм можно повторять много раз, чтобы повысить его точность. Это соответствует требованиям к рандомизированному алгоритму связи.

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

Пример: GH

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

${ displaystyle { text {GH}} _ {n} (x, y): = { begin {case} -1 & langle x, y rangle leq - { sqrt {n}} + 1 & langle x, y rangle geq { sqrt {n}}. end {case}}}$

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

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

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

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

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

Рассмотрим какой-нибудь случайный протокол п с максимальной частотой ошибок 0,1. Позволять ${ displaystyle R}$ быть ${ displaystyle 100n}$ строки длины п, пронумерованный ${ displaystyle r_ {1}, r_ {2}, dots, r_ {100n}}$. Учитывая такой ${ displaystyle R}$, определите новый протокол ${ displaystyle P '_ {R}}$ который случайно выбирает некоторые ${ displaystyle r_ {i}}$ а затем бежит п с помощью ${ displaystyle r_ {i}}$ как общая случайная строка. Занимает О(журнал 100п) = О(журналп) бит, чтобы сообщить о выборе ${ displaystyle r_ {i}}$.

Определим ${ Displaystyle р (х, у)}$ и ${ Displaystyle р '_ {R} (х, у)}$ быть вероятностями, что ${ displaystyle P}$ и ${ displaystyle P '_ {R}}$ вычислить правильное значение для ввода ${ Displaystyle (х, у)}$.

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

${ Displaystyle Pr _ {R} [| p '_ {R} (x, y) -p (x, y) | geq 0,1] Leq 2 exp (-2 (0,1) ^ {2} cdot 100n) <2 ^ {- 2n}}$

Таким образом, когда у нас нет ${ Displaystyle (х, у)}$ исправлено:

${ Displaystyle Pr _ {R} [ существует (x, y): , | p '_ {R} (x, y) -p (x, y) | geq 0,1] leq sum _ { (x, y)} Pr _ {R} [| p '_ {R} (x, y) -p (x, y) | geq 0.1] < sum _ {(x, y)} 2 ^ {-2n} = 1}$

Последнее равенство выше справедливо, потому что есть ${ displaystyle 2 ^ {2n}}$ разные пары ${ Displaystyle (х, у)}$. Поскольку вероятность не равна 1, есть некоторые ${ displaystyle R_ {0}}$ так что для всех ${ Displaystyle (х, у)}$:

${ displaystyle | p '_ {R_ {0}} (x, y) -p (x, y) | <0,1}$

поскольку ${ displaystyle P}$ имеет вероятность ошибки не более 0,1, ${ displaystyle P '_ {R_ {0}}}$ может иметь вероятность ошибки не более 0,2.

Сложность квантовой коммуникации

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

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

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

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

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

Недетерминированная коммуникационная сложность

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

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

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

Сложность связи с неограниченными ошибками

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

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

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

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

Открытые проблемы

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

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

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

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

Приложения

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

Смотрите также

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

Заметки

использованная литература

• Кушилевиц, Эял; Нисан, Ноам (2006). Коммуникационная сложность. Кембридж: Издательство Кембриджского университета. ISBN  978-0-521-02983-4. OCLC  70764786.
• Брассар, Г. Квантовая коммуникационная сложность: обзор. https://arxiv.org/abs/quant-ph/0101005
• Дицфельбингер, М., Дж. Хромкович, Дж., И Г. Шнитгер ".Сравнение двух методов нижней границы сложности коммуникации ", Теорет. Вычисл. Науки, 168, 1996. 39-51.
• Раз, Ран. «Сложность схем и коммуникаций». В теории вычислительной сложности. Стивен Рудич и Ави Вигдерсон, ред. Институт перспективных исследований Американского математического общества, 2004. 129–137.
• А. С. Яо, "Некоторые вопросы сложности, связанные с распределенными вычислениями", Proc. 11-го КБП, стр. 209–213, 1979. 14
• И. Ньюман, Частные и обычные случайные биты в сложности связи, Информационные письма 39, 1991, стр. 67–71.