Сложность многостороннего общения - Википедия - Multiparty communication complexity

В теоретическая информатика, сложность многостороннего общения это изучение сложность коммуникации в сеттинге, где более 2 игроков.

В традиционном двухпартийном коммуникационная игра, представлен Яо (1979),^[1] два игрока, п₁ и п₂ попытаться вычислить логическую функцию

${ displaystyle f (x_ {1}, x_ {2}): {0,1 } ^ {n} to {0,1 }, x_ {1}, x_ {2} in {0,1 } ^ {n '}, 2n' = n}$

Игрок п₁ знает ценность Икс₂, п₂ знает ценность Икс₁, но п_я не знает ценности Икс_я, за я = 1, 2.

Другими словами, игроки знают переменные друг друга, но не свои собственные. Минимальное количество битов, которые должны быть переданы игрокам для вычисления ж это сложность коммуникации из ж, обозначаемыйκ(ж).

Многопартийная коммуникационная игра, определенная в 1983 году,^[2] представляет собой мощное обобщение двухстороннего случая: здесь игроки знают все, что делают другие, кроме своего собственного. Из-за этого свойства иногда эту модель называют моделью «чисел на лбу», поскольку, если бы игроки сидели за круглым столом, каждый из которых носил свой ввод на лбу, то каждый игрок видел бы ввод всех остальных, кроме их собственный.

Формальное определение выглядит следующим образом: k игроки: п₁,п₂,...,п_k намереваются вычислить логическую функцию

${ displaystyle f (x_ {1}, x_ {2}, ldots, x_ {n}): {0,1 } ^ {n} to {0,1 }}$

На съемочной площадке S = {Икс₁,Икс₂,...,Икс_п} переменных существует фиксированное разделение А из k классы А₁,А₂,...,А_k, и игрок п₁ знает каждую переменную, Кроме те в А_я, за я = 1,2,...,k. У игроков есть неограниченные вычислительные возможности, и они общаются с помощью доски, которую видят все игроки.

Цель состоит в том, чтобы вычислить ж(Икс₁,Икс₂,...,Икс_п), так что в конце вычисления это значение знает каждый игрок. Стоимость вычисления - это количество бит, записанных на доску для данного ввода. Икс = (Икс₁,Икс₂,...,Икс_п) и раздел А = (А₁,А₂,...,А_k). Стоимость многостороннего протокола - это максимальное количество передаваемых битов для любого Икс из набора {0,1}^п и данный раздел А. В kсложность межпартийного общения, C^(k)_А(ж), функции ж, относительно разбиения А, - минимум затрат тех k-партийные протоколы, которые вычисляют ж. В k-сторонняя симметричная коммуникационная сложность ж определяется как

${ Displaystyle C ^ {(k)} (е) = max _ {A} C_ {A} ^ {(k)} (f)}$

где берется максимум по всем k-разбиения набора Икс = (Икс₁,Икс₂,...,Икс_п).

Верхняя и нижняя границы

Для общей оценки сверху как для двух, так и для более игроков предположим, что А₁ один из самых маленьких классов разбиения А₁,А₂,...,А_k. потом п₁ может вычислить любую булеву функцию от S с |А₁| + 1 бит связи: п₂ записывает |А₁| кусочки А₁ на доске, п₁ читает его, вычисляет и объявляет значение ж(Икс). Итак, мы можем написать:

${ displaystyle C ^ {(k)} (f) leq { bigg lfloor} {n over k} { bigg rfloor} +1.}$

Функция обобщенного внутреннего продукта (GIP)^[3] определяется следующим образом: Пусть у₁,у₂,...,у_k быть п-битовые векторы, и пусть Y быть п раз k матрица с k столбцами в качестве у₁,у₂,...,у_k векторов. Тогда ГИП (у₁,у₂,...,у_k) - количество строк матрицы, состоящей из всех единиц. Yпо модулю 2. Иными словами, если векторы у₁,у₂,...,у_k соответствуют характеристические векторы из k подмножества п элементной базы, то ГИП соответствует паритет пересечения этих k подмножества.

Было показано^[3] который

${ displaystyle C ^ {(k)} (GIP) geq c {n over 4 ^ {k}},}$

с постояннымc > 0.

Верхняя граница сложности многостороннего взаимодействия GIP показывает^[4] который

${ displaystyle C ^ {(k)} (GIP) leq c {n over 2 ^ {k}},}$

с постоянным c > 0.

Для общей булевой функции ж, можно ограничить сложность многостороннего общения ж используя его L₁ норма^[5] следующее:^[6]

${ Displaystyle С ^ {(к)} (е) = О { Bigg (} к ^ {2} log (nL_ {1} (f)) { Bigg lceil} {nL_ {1} ^ {2 } (е) более 2 ^ {k}} { Bigg rceil} { Bigg)}}$

Сложность многостороннего общения и генераторы псевдослучайных ситуаций

Построение генератора псевдослучайных чисел было основано на нижней границе BNS для функции GIP.^[3]