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

В теоретической информатике , сложность коммуникации изучает количество коммуникации требуется , чтобы решить проблему , когда вход задачи распределяется между двумя или более сторонами. Изучение сложности связи было впервые введено Эндрю Яо в 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(f)=}$ минимальное количество бит, которыми обмениваются Алиса и Боб в худшем случае.

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

Более формально набор называется (комбинаторным) прямоугольником, если когда-либо и тогда . Эквивалентно, это комбинаторный прямоугольник, если его можно выразить как для некоторых и . Рассмотрим случай, когда биты уже обмениваются между сторонами. Теперь, в частности , определим матрицу${\displaystyle R\subseteq X\times 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\times N}$${\displaystyle M\subseteq X}$${\displaystyle N\subseteq Y}$${\displaystyle k}$${\displaystyle h\in \{0,1\}^{k}}$

${\displaystyle T_{h}=\{(x,y):{\text{ the }}k{\text{-bits exchanged on input }}(x,y){\text{ is }}h\}}$

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

Пример: ${\displaystyle EQ}$[ изменить ]

Мы рассматриваем случай, когда Алиса и Боб пытаются определить, равны ли их входные строки. Формально определить Равенства функцию, обозначенную , по IFF . Как мы продемонстрируем ниже, решение любого детерминированного протокола связи в худшем случае требует битов связи. В качестве примера разминки рассмотрим простой случай . Функция равенства в этом случае может быть представлена ​​следующей матрицей. Строки представляют все возможности , столбцы - возможности .${\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 x,y\in \{0,1\}^{3}}$${\displaystyle x}$${\displaystyle y}$

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

Теорема: ${\displaystyle D(EQ)=n}$[ править ]

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

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

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

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

Рандомизированный протокол для функции имеет двустороннюю ошибку.${\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 (log n) дополнительных битов по сравнению с исходным.

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

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

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

Пример: EQ [ править ]

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

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

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

${\displaystyle {\begin{cases}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{cases}}}$

Если x и y совпадают, эти условия одинаково влияют на скалярные произведения. Мы можем спокойно игнорировать эти термины и смотреть только на то, где различаются x и y . Кроме того, мы можем поменять места бит и без изменения или нет точечных продукты равны. Это означает, что мы можем поменять местами биты, чтобы x содержал только нули, а y содержал только единицы:${\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{cases}}}$

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

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

Пример: GH [ править ]

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

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

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

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

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

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

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

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

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

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

${\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 (x,y)}$

${\displaystyle \Pr _{R}[\exists (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}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Открытые задачи [ править ]

С учетом входной матрицы 0 или 1 минимальное количество битов, которыми обмениваются для детерминированного вычисления в худшем случае , как известно, ограничено снизу логарифмом ранга матрицы . Гипотеза логарифмического ранга предполагает, что коммуникационная сложность ,, ограничена сверху постоянной степенью логарифма ранга . Поскольку D (f) ограничено сверху и снизу многочленами логранга , можно сказать, что D (f) полиномиально связано с логрангом${\displaystyle M_{f}=[f(x,y)]_{x,y\in \{0,1\}^{n}}}$${\displaystyle f}$${\displaystyle D(f)}$${\displaystyle M_{f}}$${\displaystyle D(f)}$${\displaystyle M_{f}}$${\displaystyle (M_{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
• Дицфельбингер, М., Дж. Хромкович, Дж., И Г. Шнитгер, " Сравнение двух методов оценки снизу для сложности связи ", Теорет. Comput. Sci. 168, 1996. 39–51.
• Раз, Ран . «Сложность схем и коммуникаций». В теории вычислительной сложности. Стивен Рудич и Ави Вигдерсон, ред. Институт перспективных исследований Американского математического общества, 2004. 129–137.
• AC Yao, "Некоторые вопросы сложности, связанные с распределенными вычислениями", Proc. 11-го КБП, стр. 209–213, 1979. 14
• И. Ньюман, Частные и обычные случайные биты в сложности связи , Информационные письма 39, 1991, стр. 67–71.