В теоретической информатике , сложность коммуникации изучает количество коммуникации требуется , чтобы решить проблему , когда вход задачи распределяется между двумя или более сторонами. Изучение сложности связи было впервые введено Эндрю Яо в 1979 году при изучении проблемы вычислений, распределенных между несколькими машинами. [1] Проблема обычно формулируется следующим образом: две стороны (традиционно называемые Алисой и Бобом ) каждая получают (потенциально разные)- битовая строка а также . Цель для Алисы , чтобы вычислить значение некоторой функции,, это зависит от обоих а также , с наименьшим количеством общения между ними.
Хотя Алиса и Боб всегда могут добиться успеха, если Боб отправит все свои -битная строка для Алисы (которая затем вычисляет функцию ), идея состоит в том, чтобы найти умные способы вычисления с менее чем биты общения. Обратите внимание, что, в отличие от теории вычислительной сложности , сложность связи не связана с объемом вычислений, выполняемых Алисой или Бобом, или размером используемой памяти , поскольку мы обычно ничего не предполагаем о вычислительной мощности Алисы или Боба.
Эта абстрактная проблема с двумя сторонами (называемая сложностью двусторонней связи) и ее общая форма с более чем двумя сторонами актуальна во многих контекстах. В СБИСЕ проектировании схем, например, один стремится свести к минимуму энергии , используемой путем уменьшения количества электрических сигналов , передаваемых между различными компонентами во время распределенных вычислений. Проблема также актуальна при изучении структур данных и оптимизации компьютерных сетей. Обзор поля можно найти в учебнике Кушилевица и Нисана (2006) .
Формальное определение
Позволять где в типичном случае мы предполагаем, что а также . Алиса держит-битовая строка в то время как Боб держит -битовая строка . Обмениваясь данными друг с другом по одному бит за раз (принимая какой-либо протокол связи, который согласован заранее), Алиса и Боб хотят вычислить значениетаким образом, что по крайней мере одна сторона знает значение в конце коммуникации. На этом этапе ответ может быть передан обратно, так что за счет одного дополнительного бита обе стороны будут знать ответ. Наихудший случай коммуникационной сложности этой коммуникационной проблемы вычислений, обозначаемый как , тогда определяется как
- минимальное количество бит, которыми обмениваются Алиса и Боб в худшем случае.
Как отмечалось выше, для любой функции , у нас есть . Используя приведенное выше определение, полезно подумать о функциикак матрица (называемая входной матрицей или коммуникационной матрицей ), где строки индексируются и столбцы . Элементы матрицы. Изначально и Алиса, и Боб имеют копию всей матрицы. (предполагая, что функция известно обеим сторонам). Тогда проблема вычисления значения функции может быть перефразирована как «обнуление» соответствующей записи матрицы. Эта проблема может быть решена, если Алиса или Боб знают и то, и другое. а также . В начале коммуникации количество вариантов выбора значения функции на входах равно размеру матрицы, т. Е.. Затем, как и когда каждая сторона передает немного к другим, количество вариантов ответа , так как это уменьшает устраняет набор строк / столбцов в результате в подматрице из.
Более формально набор называется (комбинаторным) прямоугольником, если всякий раз а также тогда . Эквивалентно, является комбинаторным прямоугольником, если его можно выразить как для некоторых а также . Рассмотрим случай, когдабиты уже обмениваются между сторонами. Теперь для конкретного, определим матрицу
Потом, , и нетрудно показать, что комбинаторный прямоугольник в .
Пример:
Мы рассматриваем случай, когда Алиса и Боб пытаются определить, равны ли их входные строки. Формально определим функцию равенства , обозначенную, от если только . Как показано ниже, решение любого детерминированного протокола связи требует биты связи в худшем случае. В качестве примера разминки рассмотрим простой случай. Функция равенства в этом случае может быть представлена следующей матрицей. Строки представляют все возможности, столбцы .
Эквалайзер | 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 только тогда, когда равно (т.е. по диагонали). Также довольно легко увидеть, как передача одного бита делит ваши возможности пополам. Если вы знаете, что первая часть равно 1, вам нужно рассмотреть только половину столбцов (где может равняться 100, 101, 110 или 111).
Теорема:
Доказательство. Предположить, что. Это означает, что существует такой, что а также у которых такая же расшифровка стенограммы связи . Поскольку эта запись определяет прямоугольник, также должно быть 1. По определению и мы знаем, что равенство верно только для когда . Получили противоречие.
Этот метод доказательства нижних границ детерминированной связи называется методом ложного набора . [2]
Рандомизированная сложность коммуникации
В приведенном выше определении нас интересует количество битов, которые должны быть детерминированно переданы между двумя сторонами. Если обеим сторонам предоставляется доступ к генератору случайных чисел, могут ли они определить значениес гораздо меньшим объемом обмена информацией? Яо в своей основополагающей статье [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 ) Бобу. (В- скалярное произведение в GF (2) .) Тогда Боб сравнивает b с. Если они совпадают, Боб соглашается, говоря, что x равно y . В противном случае он отвергает.
Очевидно, что если , тогда , так . Если x не равно y , возможно, что, что даст Бобу неправильный ответ. Как это произошло?
Если x и y не равны, они должны различаться в некоторых местах:
Где x и y согласны,поэтому эти термины в равной степени влияют на скалярные произведения. Мы можем спокойно игнорировать эти термины и смотреть только на то, где различаются x и y . Кроме того, мы можем поменять местами биты а также без изменения того, равны ли скалярные произведения. Это означает, что мы можем поменять местами биты, чтобы x содержал только нули, а y содержал только единицы:
Обратите внимание, что а также . Теперь возникает вопрос: для некоторой случайной строки, какова вероятность того, что ? Поскольку каждый с равной вероятностью будет 0 или1 эта вероятность равна. Таким образом, когда x не равно y ,. Алгоритм можно повторять много раз, чтобы повысить его точность. Это соответствует требованиям к рандомизированному алгоритму связи.
Это показывает, что если Алиса и Боб совместно используют случайную строку длины n , они могут послать один бит друг другу для вычисления. В следующем разделе показано, что Алиса и Боб могут обмениваться толькобиты, которые так же хороши, как и случайная строка длины n . Как только это будет показано, следует, что EQ можно вычислить в Сообщения.
Пример: GH
Чтобы получить еще один пример сложности рандомизированной связи, мы обратимся к примеру, известному как проблема Гэпа-Хэмминга (сокращенно GH ). Формально Алиса и Боб поддерживают двоичные сообщения,и хотел бы определить, очень ли похожи строки или нет. В частности, они хотели бы найти протокол связи, требующий передачи как можно меньшего количества битов для вычисления следующей частичной булевой функции,
Ясно, что они должны передавать все свои биты, если протокол должен быть детерминированным (это потому, что, если есть детерминированное строгое подмножество индексов, которые Алиса и Боб передают друг другу, то представьте, что у этого набора есть пара строк. не согласен в позиции. Если другое разногласие возникает в какой-либо позиции, которая не передается, это влияет на результат, и, следовательно, приведет к неправильной процедуре.
Тогда возникает естественный вопрос: разрешено ли нам ошибаться? времени (в случайных случаях нарисованный равномерно случайным образом из ), тогда можем ли мы обойтись протоколом с меньшим количеством битов? Оказывается, ответ несколько неожиданно отрицательный из-за результата Чакрабарти и Регева в 2012 году: они показывают, что для случайных случаев любая процедура, которая является правильной, по крайней мере, времени должен отправить битов коммуникации, то есть практически все из них.
Публичные монеты против частных монет
Легче создавать случайные протоколы, когда обе стороны имеют доступ к одной и той же случайной строке (протокол общей строки). Эти протоколы по-прежнему можно использовать, даже если обе стороны не используют случайную строку (протокол частной строки) с небольшими затратами на связь. Любой протокол случайных строк с разделяемой строкой, использующий любое количество случайных строк, можно смоделировать с помощью протокола частных строк, который использует дополнительные O (log n) бит.
Интуитивно мы можем найти некоторый набор строк, в котором достаточно случайности для запуска случайного протокола с небольшим увеличением ошибки. Этот набор можно совместно использовать заранее, и вместо того, чтобы рисовать случайную строку, Алисе и Бобу нужно только согласовать, какую строку выбрать из общего набора. Этот набор достаточно мал, чтобы можно было эффективно сообщить о выборе. Далее следует формальное доказательство.
Рассмотрим некоторый случайный протокол P с максимальной частотой ошибок 0,1. Позволять быть строки длины n , пронумерованные. Учитывая такой, определите новый протокол который случайным образом выбирает некоторые а затем запускает P, используякак общая случайная строка. Требуется O (log 100 n ) = O (log n ) бит, чтобы сообщить о выборе.
Определим а также быть вероятностями, что а также вычислить правильное значение для ввода .
Для фиксированного , мы можем использовать неравенство Хёффдинга, чтобы получить следующее уравнение:
Таким образом, когда у нас нет фиксированный:
Последнее равенство выше справедливо, потому что есть разные пары . Поскольку вероятность не равна 1, существует некоторая так что для всех :
С имеет вероятность ошибки не более 0,1, может иметь вероятность ошибки не более 0,2.
Сложность квантовой коммуникации
Сложность квантовой связи пытается количественно оценить сокращение связи, возможное за счет использования квантовых эффектов во время распределенных вычислений.
Было предложено по крайней мере три квантовых обобщения сложности коммуникации; для обзора см. текст, предложенный Г. Брассаром.
Первая - это модель связи с кубитами , в которой стороны могут использовать квантовую связь вместо классической связи, например, обмениваясь фотонами через оптическое волокно .
Во второй модели связь по-прежнему осуществляется с помощью классических битов, но сторонам разрешено манипулировать неограниченным количеством квантовых запутанных состояний в рамках своих протоколов. Выполняя измерения своих запутанных состояний, стороны могут сэкономить на классической коммуникации во время распределенных вычислений.
Третья модель включает доступ к ранее совместно используемой запутанности в дополнение к обмену кубитами и является наименее изученной из трех квантовых моделей.
Недетерминированная коммуникационная сложность
При недетерминированной сложности связи Алиса и Боб имеют доступ к оракулу. Получив слово оракула, стороны общаются, чтобы вывести. Недетерминированная коммуникационная сложность тогда максимальна по всем парам. по сумме количества обменяемых битов и длины кодирования слова оракула.
С другой стороны, это равносильно покрытию всех 1-элементов 0/1-матрицы комбинаторными 1-прямоугольниками (т. Е. Несмежными невыпуклыми подматрицами, все элементы которых равны единице (см. Кушилевитц и Нисан или Дицфельбингер и др. )). Недетерминированная коммуникационная сложность - это двоичный логарифм числа прямоугольников, покрывающих матрицу: минимальное количество комбинаторных 1-прямоугольников, необходимых для покрытия всех 1-элементов матрицы, без покрытия каких-либо 0-элементов.
Недетерминированная коммуникационная сложность возникает как средство получения нижних оценок для детерминированной коммуникационной сложности (см. Дицфельбингер и др.), Но также и в теории неотрицательных матриц, где она дает нижнюю границу неотрицательного ранга неотрицательной матрицы. [3]
Сложность связи с неограниченными ошибками
В настройке неограниченной ошибки Алиса и Боб имеют доступ к частной монете и своим собственным входам. . В этой настройке Алиса преуспеет, если она ответит правильным значениемс вероятностью строго больше 1/2. Другими словами, если ответы Алисы есть любой ненулевой корреляции к истинному значению, то протокол считается действительным.
Обратите внимание, что требование, чтобы монета была частной, очень важно. В частности, если количество общедоступных битов, совместно используемых Алисой и Бобом, не учитывается при оценке сложности связи, легко утверждать, что вычисление любой функции имееткоммуникационная сложность. [4] С другой стороны, обе модели эквивалентны, если количество общедоступных битов, используемых Алисой и Бобом, засчитывается против общего обмена данными протокола. [5]
Хотя и тонкие, нижние границы этой модели чрезвычайно сильны. В частности, ясно, что любая оценка проблем этого класса немедленно влечет за собой эквивалентные ограничения для проблем в детерминированной модели, а также в частных и публичных моделях монет, но такие ограничения также немедленно выполняются для недетерминированных моделей коммуникации и моделей квантовой коммуникации. [6]
Форстер [7] был первым, кто доказал явные нижние оценки для этого класса, показав, что вычисление скалярного произведения требует, по крайней мере битов коммуникации, хотя более ранний результат Алона, Франкла и Рёдля доказал, что сложность коммуникации почти для всех булевых функций является . [8]
Открытые проблемы
Рассматривая входную матрицу 0 или 1 , минимальное количество битов, обмениваемых для вычисления детерминированно в худшем случае, , как известно, ограничена снизу логарифмом ранга матрицы. Гипотеза логарифмического ранга предполагает, что коммуникационная сложность,, ограничена сверху постоянной степенью логарифма ранга . Поскольку D (f) ограничена сверху и снизу многочленами логранга, можно сказать, что D (f) полиномиально связана с лог-рангом. Поскольку ранг матрицы является полиномиальным вычислимым по размеру матрицы, такая верхняя граница позволит аппроксимировать коммуникационную сложность матрицы за полиномиальное время. Обратите внимание, однако, что размер самой матрицы экспоненциально зависит от размера входных данных.
Предполагается, что для рандомизированного протокола количество битов, которыми обмениваются в худшем случае, R (f), полиномиально связано со следующей формулой:
Такие предположения о логарифмическом ранге ценны, потому что они сводят вопрос о сложности связи матрицы к вопросу о линейно независимых строках (столбцах) матрицы. Это показывает, что суть проблемы сложности связи, например, в приведенном выше случае EQ, заключается в том, чтобы выяснить, где в матрице находятся входные данные, чтобы выяснить, эквивалентны ли они.
Приложения
Нижние границы сложности связи могут использоваться для доказательства нижних границ сложности дерева решений , схем СБИС , структур данных, потоковых алгоритмов , пространственно-временных компромиссов для машин Тьюринга и многого другого. [2]
Смотрите также
Заметки
- ^ a b Яо, AC (1979), "Некоторые вопросы сложности, связанные с распределительными вычислениями", Proc. 11-го созыва , 14 : 209–213
- ^ а б Кушилевиц, Эяль; Нисан, Ноам (1997). Коммуникационная сложность . Издательство Кембриджского университета. ISBN 978-0-521-56067-2.
- ^ Яннакакис, М. (1991). «Выражение задач комбинаторной оптимизации линейными программами» . J. Comput. Syst. Sci . 43 (3): 441–466. DOI : 10.1016 / 0022-0000 (91) 90024-у .
- ^ Ловетт, Шахар, CSE 291: сложность связи, протоколы неограниченных ошибок зимы 2019 г. (PDF) , получено 9 июня 2019 г.
- ^ Гёш, Мика; Питасси, Тониан; Уотсон, Томас (2018-06-01). «Пейзаж классов сложности общения» . Вычислительная сложность . 27 (2): 245–304. DOI : 10.1007 / s00037-018-0166-6 . ISSN 1420-8954 . S2CID 4333231 .
- ^ Шерстов, Александр Александрович (октябрь 2008 г.). «Коммуникационная сложность симметричных функций с неограниченной ошибкой». 2008 49-й ежегодный симпозиум IEEE по основам информатики : 384–393. DOI : 10.1109 / focs.2008.20 . ISBN 978-0-7695-3436-7. S2CID 9072527 .
- ^ Форстер, Юрген (2002). «Линейная нижняя граница вероятностной сложности связи с неограниченной ошибкой» . Журнал компьютерных и системных наук . 65 (4): 612–625. DOI : 10.1016 / S0022-0000 (02) 00019-3 .
- ^ Alon, N .; Frankl, P .; Родл, В. (октябрь 1985 г.). «Геометрическая реализация заданных систем и вероятностная коммуникационная сложность». 26-й ежегодный симпозиум по основам информатики (SFCS 1985) . Портленд, штат Орегон, США: IEEE: 277–280. CiteSeerX 10.1.1.300.9711 . DOI : 10.1109 / SFCS.1985.30 . ISBN 9780818606441. S2CID 8416636 .
Рекомендации
- Кушилевиц, Эяль; Нисан, Ноам (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.