Сложность многосторонней связи

В информатике теоретической сложность многосторонней коммуникации — это исследование сложности коммуникации в условиях, когда участвуют более двух игроков.

В традиционной игре с двусторонним общением , предложенной Яо (1979) , два игрока, P1 _, и P2 _{пытаются} вычислить булеву функцию

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

Игрок P1 _, значение x2 _но , P2 _{= 1} значение x1 _i знает Pi _не знает значения xi _, поскольку знает , 2.

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

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

Формальное определение следующее: $k$ игроки: $P_{1},P_{2},...,P_{k}$ намерены вычислить логическую функцию

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

На съемочной площадке $S=\{x_{1},x_{2},...,x_{n}\}$ переменных существует фиксированный раздел $A$ из $k$ занятия $A_{1},A_{2},...,A_{k}$и игрок $P_{1}$ знает каждую переменную, кроме тех, которые находятся в $A_{i}$, для $i=1,2,...,k$. Игроки обладают неограниченной вычислительной мощностью и общаются с помощью доски, которую просматривают все игроки.

Цель состоит в том, чтобы вычислить $f(x_{1},x_{2},...,x_{n}$), так что в конце вычислений каждый игрок знает это значение. Стоимость вычислений — это количество битов, записанных на доске для данного входного сигнала. $x=(x_{1},x_{2},...,x_{n})$ и раздел $A=(A_{1},A_{2},...,Ax_{n})$. Стоимость многостороннего протокола — это максимальное количество битов, передаваемых для любого $x$ из набора {0,1} ^н и данный раздел $A$. $k$-сложность партийного общения, $C_{A}^{(k)}(f)$ функции $f$, относительно раздела $A$, – минимум затрат тех $k$-партийные протоколы, которые вычисляют $f$. $k$-партийная симметричная сложность связи $f$ определяется как

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

где максимум берется по всем k -разбиениям множества $x=(x_{1},x_{2},...,x_{n})$.

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

более игроков предположим, что A ₁ — один из наименьших классов разбиения A ₁ , A ₂ ,..., Ak _{Для общей верхней оценки как для двух, так и для} . Тогда P ₁ может вычислить любую булеву функцию от S с | А ₁ | + 1 бит связи: P ₂ записывает | А ₁ | биты A ₁ на доске, P ₁ читает их, вычисляет и объявляет значение $f(x)$. Итак, можно написать следующее:

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

Функция обобщенного внутреннего продукта (GIP) определяется следующим образом:Позволять $y_{1},y_{2},...,y_{k}$ быть $n$-битовые векторы, и пусть $Y$ быть $n$ раз $k$ матрица, с $k$ столбцы как $y_{1},y_{2},...,y_{k}$ векторы. Затем $GIP(y_{1},y_{2},...,y_{k})$ - количество строк матрицы, состоящих из всех 1 $Y$, взятый по модулю 2. Другими словами, если векторы $y_{1},y_{2},...,y_{k}$ соответствуют векторам характеристическим $k$ подмножества $n$ элемент base-set, то GIP соответствует четности пересечения этих $k$ подмножества.

Было показано что

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

с константой с > 0.

Верхняя граница сложности многосторонней связи в GIP показывает что

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

с константой с > 0.

Для общей булевой функции f можно ограничить сложность многосторонней связи f, используя ее L _1. норму следующее:

$C^{(k)}(f)=O{\Bigg (}k^{2}\log(nL_{1}(f)){\Bigg \lceil }{nL_{1}^{2}(f) \over 2^{k}}{\Bigg \rceil }{\Bigg )}$

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

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