Коммуникационная сложность: различия между версиями

В [[Теоретическая информатика|теоретической информатике]] '''коммуникационная сложность''' изучает количество коммуникации, необходимое для решения задачи, условие которой [[Распределённые вычисления|распределено]] между двумя или более сторонами. Это понятие было введено [[Яо, Эндрю|Эндрю Яо]] в 1979 году<ref name="yao1979">{{Citation|last=Yao|first=A. C.|title=Some Complexity Questions Related to Distributed Computing|journal=Proc. of 11th STOC|volume=14|pages=209–213|year=1979}}</ref>, который исследовал следующую задачу для двух участников, традиционно называемых [[Алиса и Боб|Алисой и Бобом]]. Алиса получает ''n-''[[Бит|битную]] строку ''x,'' а Bob — ''n-''битную строку ''y'', и их цель состоит в том, чтобы один из них (например, Боб) вычислил определенную и известную обоим участникам функцию <math>f(x,y)</math>, при этом с наименьшим количеством [[Общение|коммуникации]] между ними. Конечно, они всегда могут вычислить <math>f(x,y)</math> следующим образом: Алиса отправляет всю свою n-битную строку Бобу, который затем вычисляет [[Функция (математика)|функцию]] <math>f(x,y)</math>. Поэтому в данной постановке задачи интересно, для каких функций ''f'' существует способ вычислить <math>f(x,y)</math> передав менее n битов. Важное отметить, что в данной задаче нас не интересует [[Вычислительная сложность|сложность вычислений,]] выполненных Алисой или Бобом, или размер используемой для этих вычислений памяти.

Эта абстрактная проблема с двумя участниками (называемая коммуникационной сложностью с двумя участниками) и ее общая форма с большим количеством участников актуальна во многих контекстах: например, при проектировании схем [[Интегральная схема|больших интегральных схем]] требуется минимизировать используемую энергию, путем уменьшения количества электрических сигналов между различными компонентами во время распределенных вычислений. Коммуникационная сложность используется также при изучении структур данных и алгоритмов, при оптимизации компьютерных сетей, в теории вычислительной сложности и сложности доказательств и в других областях. Для обзора области см. {{Harvtxt|Kushilevitz|Nisan|2006}} .