Complexité de la communication

La complexité de la communication ou complexité de communication est une notion étudiée en informatique théorique. Le dispositif abstrait classique est le suivant : Alice et Bob ont chacun un message, et ils veulent calculer un nouveau message à partir de leurs messages, en se transmettant un minimum d'information. Par exemple, Alice et Bob reçoivent un mot chacun, et ils doivent décider s'ils ont reçu le même mot ; ils peuvent bien sûr s'envoyer leur mot l'un à l'autre et comparer, mais la question est de minimiser le nombre de messages.

Utiliser une ressources en communication est le fait d'envoyer une information à l'autre. Alice peut ainsi envoyer la première lettre de son mot à bob, ceci a un coût de 1.

La théorie de la complexité de communication a donc pour but de calculer quelles sont les ressources en communication nécessaires pour effectuer certaines tâches dans un contexte de calcul distribué. Contrairement à la théorie de la complexité classique, on ne compte pas les ressources nécessaires aux calculs (temps et espace par exemple).

Cette notion a été définie en 1979 par Andrew Yao et est utilisée notamment pour l'étude des algorithmes en ligne et le design des circuits VLSI.

Définitions formelles

Protocole

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

Un protocole qui calcule $f$ est une décomposition d'étapes. Dans chaque étape, Alice (resp. Bob) calcule en fonction de son entrée $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 $A$ si c'est Alice qui calcule ou $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.

Un arbre pour le protocole de EQ2

Complexité d'un protocole

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.

Les différentes formes

Cas déterministe

Dans le cas déterministe la complexité de communication d'une fonction $f$, notée $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.

Cas probabiliste

Dans le cas probabiliste, on note la complexité $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).

Cas quantique

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.

Bornes inférieures

Dans la théorie de la complexité plus classique, prouver des bornes inférieures sur la difficulté des problèmes peut se révéler très difficile, comme l'illustre le problème P=NP. Il est parfois facile d'obtenir des bornes inférieures pour la complexité de la communication. Pour cela, il existe deux méthodes classiques.

Rectangles combinatoires

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

$\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 $A$ (rep. $B$) l'ensemble des éléments de $X$ (resp. $Y$) tel qu'un élément de $Y$ (rep. $X$), tous les éléments ($x$,$y$) ont la même réponse. L'idée est que le $x$ (resp. $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 $log_{2}n$.

Rang de la matrice

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

La propriété de Logrank est la suivante:

$\forall f:X\times Y->\{0;1\}$ le coût minimal d'un protocole est $log(rangM_{f})$

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

Exemples

L’égalité

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

Un protocole simple est qu’Alice envoie $x$ à Bob, et que Bob calcule le résultat et le renvoie. Ce protocole a un coût de $n+1$ (Alice envoie $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).

La disjonction

On veut calculer $DISJ_{n}(x,y)$, qui vaut 1 si $x\cap y=\emptyset$ (où $x$ et $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 $x$ à Bob, et que Bob renvoie le résultat. La complexité est à nouveau de $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).

Historique

Andrew Yao

La complexité de la communication a été inventée en 1979 par Andrew Yao dans l'article Some Complexity Questions Related to Distributed Computing. Yao a reçu le prix Turing en 2000 pour ses travaux, notamment dans ce domaine.

Applications

Les résultats de complexité de communication sont utilisés sur dans le domaine théorique pour faire le lien entre les bornes inférieures issues de différents modèles de calculs comme les machines de Turing, les arbres de décision, les branching programs etc. ; on en a vu un exemple ci-dessus.

On peut aussi obtenir des bornes pour les algorithmes de fouille de données et les algorithmes en ligne.

Exemple : Taille minimale d’un automate

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 $A=\left(Q,q_{0},F,\delta \right)$ qui reconnait le langage $\left\{xx:x\in \{0,1\}^{n}\right\}$. On peut alors construire un protocole pour $EQ_{n}$ avec $\lceil log_{2}(|Q|)\rceil +1$ bits de communication :

• Alice exécute l’automate $A$ sur $x$
• Alice transmet le numéro de l’état de A après l’exécution à Bob : $\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 $x=y$ en testant si l’automate est dans un état final ou non.

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

Bibliographie

Articles

• 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

Ouvrages

• 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)

Liens externes

• Conférence au collège de France de Bernard Chazelle sur le thème de la complexité de la communication (15 novembre 2012).