Complexité de la communication

Soit trois ensembles ${\displaystyle X}$, ${\displaystyle Y}$ et ${\displaystyle Z}$, et une fonction ${\displaystyle f:X\times Y\mapsto Z}$, typiquement ${\displaystyle X=Y=\{0,1\}^{n}}$ et ${\displaystyle Z=\{0,1\}}$. Alice reçoit un élément de ${\displaystyle x\in X}$ et Bob un élément de ${\displaystyle y\in Y}$, et ils veulent calculer ${\displaystyle z=f(x,y)}$ (Alice et Bob sont appelés les « joueurs »).

Un protocole qui calcule ${\displaystyle f}$ est une décomposition d'étapes. Dans chaque étape, Alice (resp. Bob) calcule en fonction de son entrée ${\displaystyle x}$ et des bits déjà échangés et décide soit de terminer car elle a fini de calculer soit d'envoyer un bit à Bob (resp. Alice). Un protocole se représente généralement sous la forme d'un arbre. Un exemple est donné ci-dessous. Les nœuds de l'arbre sont étiquetés ${\displaystyle A}$ si c'est Alice qui calcule ou ${\displaystyle B}$ si c'est Bob. Les arêtes sont étiquetées 1 si le bit envoyé vaut 1 et zéro s'il vaut zéro.

Selon les modèles, on peut accepter un protocole qui est correct seulement avec une bonne probabilité ou utilisant même des bits quantiques. Il existe aussi des généralisations avec plus de deux joueurs[1].

Un arbre pour le protocole de EQ2

La complexité d'un protocole est le nombre de bit échangés dans le pire cas. Sur l'arbre représentant le protocole, la complexité du protocole est la profondeur de l’arbre.

Sur l'exemple précédent, le protocole a un coût de trois.

Dans le cas déterministe la complexité de communication d'une fonction ${\displaystyle f}$, notée ${\displaystyle D(f)}$, est le nombre de bits échangés en utilisant un protocole déterministe. C'est la notion la plus classique, et la plus restrictive des trois notions définies ici.

Dans le cas probabiliste, on note la complexité ${\displaystyle R(f)}$ (pour randomized). Dans ce cas Alice et Bob peuvent utiliser des sources de bits aléatoires pour faire leur calculs (comme pour les algorithmes probabilistes), et le protocole est considéré satisfaisant si la probabilité d'une bonne réponse est supérieure à une certaine constante. Selon le modèle, les joueurs peuvent partager leurs sources de bits aléatoires (on parle alors de public coin protocol) ou pas (private coin protocol).

Il existe plusieurs modèles de complexité de la communication utilisant les notions d'informatique quantique, notamment par l'échange de qubits à la place des bits, ou encore le partage de qubit intriqués.

Un rectangle combinatoire est le produit d'un sous ensemble ${\displaystyle U}$ de ${\displaystyle X}$ et d'un sous ensemble ${\displaystyle V}$ de ${\displaystyle Y}$ tel que:

${\displaystyle \forall x\in U,\forall v\in V,f(u,v)=1}$

Un protocole crée une partition en rectangle combinatoire grâce au fait que l'ensemble des éléments est un rectangle combinatoire. En appelant ${\displaystyle A}$ (rep. ${\displaystyle B}$) l'ensemble des éléments de ${\displaystyle X}$ (resp. ${\displaystyle Y}$) tel qu'un élément de ${\displaystyle Y}$ (rep. ${\displaystyle X}$), tous les éléments (${\displaystyle x}$,${\displaystyle y}$) ont la même réponse. L'idée est que le ${\displaystyle x}$ (resp. ${\displaystyle y}$) conduit à la feuille pour les nœuds d'Alice (resp. Bob).

Ainsi si on prouve qu'il n'existe pas de partition en moins de n rectangles combinatoires, alors le coût minimal d'un protocole est au moins ${\displaystyle log_{2}n}$.

Le rang de la matrice ci-dessus est aussi une source de bornes inférieur.

La propriété de Logrank est la suivante:

${\displaystyle \forall f:X\times Y->\{0;1\}}$

le coût minimal d'un protocole est ${\displaystyle log(rangM_{f})}$

La réciproque est une conjecture et n'a pas été démontré à l'heure actuelle.

On veut calculer ${\displaystyle EQ_{n}(x,y)}$, qui vaut 1 si ${\displaystyle x=y}$ et 0 sinon.

Un protocole simple est qu’Alice envoie ${\displaystyle x}$ à Bob, et que Bob calcule le résultat et le renvoie. Ce protocole a un coût de ${\displaystyle n+1}$ (Alice envoie ${\displaystyle n}$ bits, et Bob doit en envoyer un). L'arbre de ce protocole est l'exemple donné précédemment.

On peut montrer que ce protocole est optimal dans le cas déterministe (ce que l’on peut montrer grâce à la propriété utilisant les rectangles combinatoires ci-dessus), mais il existe un protocole plus efficace dans le cas probabiliste^{[réf. nécessaire]} (qui fait appel à une fonction de hashage).

On veut calculer ${\displaystyle DISJ_{n}(x,y)}$, qui vaut 1 si ${\displaystyle x\cap y=\emptyset }$ (où ${\displaystyle x}$ et ${\displaystyle y}$ sont interprétés comme un tableau de booléens définissant des ensembles) et 0 sinon.

Un protocole simple est, comme précédemment, qu’Alice envoie ${\displaystyle x}$ à Bob, et que Bob renvoie le résultat. La complexité est à nouveau de ${\displaystyle n+1}$.

Ce protocole est optimal dans le cas déterministe, mais il existe un meilleur algorithme dans le cas probabiliste (mais lui aussi linéaire)[2].

Un exemple d’application de la complexité de la communication est une preuve de borne inférieure sur le nombre d’états d’un automate fini.

On suppose que l’on a un automate ${\displaystyle A=\left(Q,q_{0},F,\delta \right)}$ qui reconnait le langage ${\displaystyle \left\{xx:x\in \{0,1\}^{n}\right\}}$. On peut alors construire un protocole pour ${\displaystyle EQ_{n}}$ avec ${\displaystyle \lceil log_{2}(|Q|)\rceil +1}$ bits de communication :

• Alice exécute l’automate ${\displaystyle A}$ sur ${\displaystyle x}$
• Alice transmet le numéro de l’état de A après l’exécution à Bob : ${\displaystyle \lceil log_{2}(|Q|)\rceil }$ bits (en donnant par exemple son indice en base 2)
• Bob termine l’exécution, et peut en déduire si ${\displaystyle x=y}$ en testant si l’automate est dans un état final ou non.

Or, on a vu que pour résoudre ${\displaystyle EQ_{n}}$, il faut au moins ${\displaystyle n+1}$ bits de communication, d’où ${\displaystyle \lceil log_{2}(|Q|)\rceil +1\geq n}$, donc ${\displaystyle log_{2}(|Q|)>n}$, donc ${\displaystyle |Q|>2^{n}}$

• Andrew Chi-Chih Yao, « Some complexity questions related to distributive computing », dans Proceedings of the eleventh annual ACM symposium on Theory of computing, 1979, p. 209-213

• Eyal Kushilevitz et Noam Nisan, Communication complexity, Cambridge University Press, 2006, 189 p. (ISBN 978-0-521-56067-2, lire en ligne)

• Marc Kaplan, Méthodes Combinatoires et Algébriques en Complexité de la Communication (thèse de doctorat en Sciences), Université Paris-Sud XI, 2009 (lire en ligne)