6.5. Коммуникационная сложность 293
сложности задач. Объединение компьютеров в локальные сети
также редко приводило к тому, что «бутылочным горлышком»
при решении какой-либо задачи являлись именно пропускная
способность сети или высокая стоимость трафика.
Однако с появлением глобальных сетей стали возникать си-
туации, когда, например, несколько мощных научных центров,
обладающих огромными вычислительными ресурсами, пыта-
ются объединить усилия для решения некоторой вычислитель-
ной задачи, либо когда филиалам транснациональной корпора-
ции требуется выполнить, возможно, алгоритмически неслож-
ные действия, но над распределенными базами данных, при
этом основной стоимостью становится стоимость коммуника-
ций. Как напрямую, путем оплаты услуг провайдера, так и опо-
средовано — когда передача больших объемов данных занима-
ет много дорогостоящего времени и тормозит вычисления.
Таким образом, появилось новое ресурсное ограничение —
стоимость коммуникации, и, соответственно, появилась новая
мера сложности алгоритмических задач — коммуникационная
сложность.
При исследовании коммуникационной сложности задачи
полагают, что входные данные некоторым образом распреде-
лены между n > 1 участниками, каждый из которых обладает
неограниченными вычислительными ресурсами, и необходимо
установить нижние и верхние оценки для трафика (объема со-
общений), необходимого для решения задачи. Существуют раз-
личные модели коммуникации, обуславливающие различные
меры коммуникационной сложности: модели с произвольным
числом участников, модели с произвольным распределением
данных и т. п. Наиболее стандартной и классической является
модель с двумя участниками и симметричным распределением
между ними входных данных
17
.
17
Как и во многих задачах, связанных с коммуникациями (например,
в криптографических постановках), этих двух участников зовут Алиса
и Боб.