Обсуждение :
В последнее время я проводил некоторое личное время, изучая различные вещи в сложности общения. Например, я повторно ознакомился с соответствующей главой в Арора / Барак, начал читать некоторые статьи и заказал книгу Кушилевица / Нисана. Интуитивно я хочу сравнить сложность коммуникации с вычислительной сложностью. И, в частности, меня поразил тот факт, что вычислительная сложность превратилась в богатую теорию размещения вычислительных задач в классы сложности, некоторые из которых, в свою очередь ( по крайней мере, с одной точки зрения ) можно представить в терминах полных задач для каждый данный класс. Например, при первом объяснении кому-то трудно избежать сравнений с SAT или какой-либо другой NP-полной проблемой.
Для сравнения, я никогда не слышал ничего подобного о классах сложности общения. Мне известно много примеров проблем, «полных для теоремы». Например, в качестве общей основы авторы могут описать данную проблему связи а затем доказать, что соответствующая теорема имеет место, проблема связи может быть решена в или менее битах (для некоторого который зависит от конкретной теоремы / проблемы). рассматриваемая пара). Терминология , используемая в литературе , то в том , что является «полной» для .T i f f X X P T
Кроме того, в черновом проекте главы Arora / Barak (который, кажется, был удален / изменен в окончательной печати) есть , в которой говорится: «В общем, протоколы связи можно рассматривать как , , и т. Д. " Тем не менее, я заметил два важных упущения:c o N P P H
- «Аналогичная» концепция, по-видимому, является способом вычисления сложности связи для решения данного протокола с доступом к различным типам ресурсов, но не может определить правильные классы сложности связи ...
- Большая часть сложности коммуникации кажется относительно «низкоуровневой», в том смысле, что подавляющее большинство результатов / теорем / и т. Д. вращаются вокруг маленьких, определенных значений полиномиального размера. Это несколько поднимает вопрос о том, почему, скажем, интересен для вычислений, но аналогичная концепция представляется менее интересной для общения. (Конечно, я мог быть просто виноват в том, что просто не знал о понятиях сложности коммуникации "более высокого уровня".)
Вопрос (ы) :
Существует ли аналогичная концепция для классов вычислительной сложности для сложности коммуникации?
И:
Если да, то как это соотносится со «стандартным» понятием классов сложности? (например, существуют ли естественные ограничения для «классов сложности связи», которые заставляют их по своей природе не соответствовать всему диапазону классов сложности вычислений?) Если нет, то в чем причина «большой картины», что классы представляют собой интересный формализм для сложности вычислений, но не для сложности общения?
Раздел Сложность зоопарка перечислены наиболее важные классы коммуникационной сложности.
источник
Фундаментальная причина, по которой существуют такие ограничения на сложность связи, заключается в том, что существует только линейный объем всей информации, которая должна быть передана (входные данные). Хотя Хартмут Клаук уже по существу указал на это в своем ответе, я хотел бы выделить ответ на другой OQ относительно основной причины этого фундаментального ограничения, а именно, что игроки не ограничены в вычислительном отношении .
Если кто-то хотел бы рассмотреть «более высокие» классы общения, то естественная вещь, на которую следует обратить внимание (вместо этого), - это сложность общения / вычислительной сложности, о которой люди точно знают и изучали в различных формах, но я думаю, что на самом деле это не так. систематически изучается. Например, при изучении интерактивных доказательств обычно учитывают влияние вычислительных ограничений игроков, хотя и не так часто, чтобы учитывать общее количество передаваемых битов. Последнее чаще встречается при изучении PCP, где, например, для PCP с поли-размером, требующим запросов, требуется только бит для передачи. КогдаO ( d ( n ) log n ) d ( n ) = O ( 1 )d(n) O(d(n)logn) d(n)=O(1) Я думаю, что обратное утверждение также по существу верно, так что сложность запросов в PCP тесно связана с этой проблемой комбинированной коммуникации / вычислительной сложности.
источник