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 ces messages, en se transmettant un minimum d'information. Par exemple, Alice et Bob reçoivent un mot chacun, et ils doivent décider si 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 savoir si on peut avoir une réponse en échangeant moins de messages.

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]

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"). Ils peuvent échanger des bits selon un certain protocole de communication, par exemple un bit chacun son tour[1].

On s’intéresse au nombre minimum de bits à échanger pour que le calcul puisse être fait. Plus précisement on considère le minimum sur tous les protocoles du nombre de bit échangés sur la pire instance (x,y).

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

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.

Un exemple : l'égalité[modifier | modifier le code]

Historique[modifier | modifier le code]

Andrew Yao

La complexité de la communication a été 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 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,‎ 1979, p. 209-213

Ouvrages[modifier | modifier le code]

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

  1. Cette définition est la définition classique, elle peut notamment être consultée dans (Kushilevitz et Nisan 2006) page 3.
  2. (Kushilevitz et Nisan 2006), chap. 6 "Multiparty Communication Complexity"
  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]