Complexité de communication multipartite – Wikipedia wiki

En informatique théorique, complexité de communication multipartite est l’étude de la complexité de la communication dans le cadre où il y a plus de 2 joueurs.

Dans le jeu de communication traditionnel à deux parties, introduit par Yao (1979), ^[d’abord] deux joueurs, P _d’abord et P ₂ tenter de calculer une fonction booléenne

${displayStyle f (x_ {1}, x_ {2}): {0,1} ^ {n} à {0,1}, x_ {1}, x_ {2} dans {0,1} ^ {n ‘ }, 2n ‘= n}$

Joueur P _d’abord connaît la valeur de X ₂ , P ₂ connaît la valeur de X _d’abord , mais P _je ne connaît pas la valeur de X _je , pour je = 1, 2.

En d’autres termes, les joueurs connaissent les variables de l’autre, mais pas les leurs. Le nombre minimum de bits qui doivent être communiqués par les joueurs pour calculer F est la complexité de la communication de F , indiqué par K ( F ).

Le jeu de communication multipartite, défini en 1983, ^[2] est une puissante généralisation du cas de 2 parties: ici, les joueurs connaissent toutes les contributions des autres, sauf les leurs. En raison de cette propriété, ce modèle est parfois appelé modèle “numéros sur le front”, car si les joueurs étaient assis autour d’une table ronde, chacun portant sa propre entrée sur le front, alors chaque joueur verrait toutes les contributions des autres, sauf les leurs.

La définition formelle est la suivante:

${displaystyle k}$

joueurs:

${displayStyle p_ {1}, p_ {2}, …, p_ {k}}$

l’intention de calculer une fonction booléenne

${displayStyle f (x_ {1}, x_ {2}, ldots, x_ {n}): {0,1} ^ {n} à {0,1}}$

Sur le plateau

${DisplayStyle s = {x_ {1}, x_ {2}, …, x_ {n}}}}$

de variables il y a une partition fixe

${displaystyle a}$

de

${displaystyle k}$

Des classes

${displayStyle a_ {1}, a_ {2}, …, a_ {k}}$

et joueur

${displayStyle p_ {1}}$

connaît chaque variable, sauf ceux de

${displayStyle a_ {i}}$

, pour

${displayStyle i = 1,2, …, k}$

. Les joueurs ont une puissance de calcul illimitée, et ils communiquent à l’aide d’un tableau noir, vu par tous les joueurs.

Le but est de calculer

${displayStyle f (x_ {1}, x_ {2}, …, x_ {n}}$

), de sorte qu’à la fin du calcul, chaque joueur connaît cette valeur. Le coût du calcul est le nombre de bits écrits sur le tableau noir pour l’entrée donnée

${DisplayStyle x = (x_ {1}, x_ {2}, …, x_ {n})}$

et partition

${displayStyle a = (a_ {1}, a_ {2}, …, ax_ {n})}$

. Le coût d’un protocole multipartite est le nombre maximum de bits communiqués pour tout

${displaystyle x}$

de l’ensemble {0,1} ⁿ et la partition donnée

${displaystyle a}$

. Le

${displaystyle k}$

– Complexité de communication en partie,

${displayStyle c_ {a} ^ {(k)} (f)}$

d’une fonction

${displaystyle f}$

, en ce qui concerne la partition

${displaystyle a}$

, est le minimum des coûts de ceux

${displaystyle k}$

-Protocoles à partie qui calculent

${displaystyle f}$

. Le

${displaystyle k}$

-Party Complexité de communication symétrique de

${displaystyle f}$

est défini comme

${displayStyle c ^ {(k)} (f) = max _ {a} c_ {a} ^ {(k)} (f)}$

où le maximum est repris k -Partitions de l’ensemble

${DisplayStyle x = (x_ {1}, x_ {2}, …, x_ {n})}$

.

Limites supérieures et inférieures [ modifier ]]

Pour une limite supérieure générale à la fois pour deux joueurs et plus, supposons que UN _d’abord est l’une des plus petites classes de la partition UN _d’abord , UN ₂ , …, UN _k . Alors P _d’abord peut calculer n’importe quelle fonction booléenne de S avec | UN _d’abord | + 1 bits de communication: P ₂ Écrit le | UN _d’abord | un peu de UN _d’abord sur le tableau noir, P _d’abord Le lit, et calcule et annonce la valeur

${displayStyle f (x)}$

. Ainsi, ce qui suit peut être écrit:

${displayStyle c ^ {(k)} (f) leq {bigg lfloor} {n sur k} {bigg rfloor} +1.}$

La fonction du produit interne généralisé (GIP) ^[3] est défini comme suit:
Laisser

${displayStyle y_ {1}, y_ {2}, …, y_ {k}}$

être

${displaystyle n}$

– Vecteurs de bits, et laissez

${displaystyle y}$

Soit le

${displaystyle n}$

fois

${displaystyle k}$

matrice, avec

${displaystyle k}$

colonnes comme le

${displayStyle y_ {1}, y_ {2}, …, y_ {k}}$

vecteurs. Alors

${DisplayStyle gip (y_ {1}, y_ {2}, …, y_ {k})}$

est le nombre des lignes de matrice tout-1

${displaystyle y}$

, pris modulo 2. En d’autres termes, si les vecteurs

${displayStyle y_ {1}, y_ {2}, …, y_ {k}}$

correspondent aux vecteurs caractéristiques de

${displaystyle k}$

sous-ensembles d’un

${displaystyle n}$

ensemble d’éléments, puis GIP correspond à la parité de l’intersection de ces

${displaystyle k}$

sous-ensembles.

Il a été montré ^[3] ce

${displayStyle c ^ {(k)} (gip) geq c {n sur 4 ^ {k}},}$

avec une constante c > 0.

Une limite supérieure de la complexité de communication multipartite des spectacles GIP ^[4] ce

${displayStyle c ^ {(k)} (gip) leq c {n sur 2 ^ {k}},}$

avec une constante c > 0.

Pour une fonction booléenne générale F , on peut lier la complexité de communication multipartite de F en utilisant son L _d’abord norme ^[5] comme suit: ^[6]

${displayStyle c ^ {(k)} (f) = o {bigg (} k ^ {2} log (nl_ {1} (f)) {bigg lceil} {nl_ {1} ^ {2} (f) 2 ^ {k}} {bigg rceil} {bigg)}}$

Complexité de communication multipartite et générateurs de pseudorandom [ modifier ]]

Une construction d’un générateur de nombres pseudo-aléatoires était basée sur la limite inférieure du BNS pour la fonction GIP. ^[3]