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.