Complexité de la communication

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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[modifier | modifier le code]

Protocole[modifier | modifier le code]

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 étapes, 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 arrêtes sont étiquetés 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 abre pour le protocole de EQ2

Complexité d'un protocole[modifier | modifier le code]

La complexité d'un protocole est le nombre de bit est le nombre de bit échangé 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[modifier | modifier le code]

Cas déterministe[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

Dans les théorie de la complexité simple (temps et espace), il existe très peu de bornes inférieur sur la complexité. Par exemple, on peut dire qu'un problème se résout en temps polynomial en trouvant un algorithme en temps polynomial. Par contre, la question de savoir si les algorithmes sont optimaux est difficiles. Le Problème P = NP est une de ces questions.

L'avantage de la théorie de la complexité est qu'elle permet de prouver des bornes inférieur facilement. Pour cela, il existe deux méthodes principales.

Rectangle combinatoires[modifier | modifier le code]

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[modifier | modifier le code]

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(rang M_f)

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

Exemples[modifier | modifier le code]

L’égalité[modifier | modifier le code]

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[modifier | modifier le code]

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)[2].

Application : taille minimale d’un automate[modifier | modifier le code]

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

Historique[modifier | modifier le code]

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[3]. Yao a reçu le prix Turing en 2000 pour ses travaux, notamment dans ce domaine[4].

Applications[modifier | modifier le code]

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[5].

Bibliographie[modifier | modifier le code]

Articles[modifier | modifier le code]

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

Ouvrages[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. (Kushilevitz et Nisan 2006), chap. 6 "Multiparty Communication Complexity"
  2. Bala Kalyanasundaram et Georg Schintger, « The Probabilistic Communication Complexity of Set Intersection », SIAM Journal on Discrete Mathematics, vol. 5,‎ , p. 545 (DOI 10.1137/0405044)
  3. (Yao 1979)
  4. Page de l'ACM sur Andrew Yao pour son prix Turing en 2000.
  5. Iordanis Kerenidis, Frédéric Magniez et David Xiao, « Complexité de communication », dans Informatique Mathématique : un photographie en 2014, Presses Universitaires de Perpignan (ISBN 978-2-35412-228-7)

Liens externes[modifier | modifier le code]