Quand Alice et Bob doivent se parler au minimum

Alice possède un message, Bob en a un autre. Ils veulent calculer quelque chose ensemble, mais avec un problème : transmettre le moins d'information possible. La complexité de la communication pose cette question élégante : combien de bits au minimum faut-il échanger pour résoudre un problème à deux? Par exemple, savoir s'ils ont reçu le même mot sans simplement se l'envoyer. Ce domaine de l'informatique théorique explore les limites du dialogue, étudiant comment économiser chaque bit transmis. Un jeu d'optimisation qui révèle des vérités profondes sur la communication elle-même.