ein Spiel, bei dem Berechnungen auf einen wesentlichen Aspekt, den der Kommunikation, reduziert werden.

Schranken für die Kommunikationskomplexität führen zu Schranken in vielen Gebieten, z. B. für VLSI-Schaltkreise und verschiedene Varianten von Branchingprogrammen. Im grundlegenden Kommunikationsspiel wollen Alice und Bob eine Boolesche Funktion f : {0, 1}^n+m → {0, 1} auswerten (Auswertungsproblem), wobei Alice die ersten n Bits der Eingabe und Bob die letzten m Bits kennt. Ihre Rechenkraft ist unbeschränkt und ihr Ziel besteht darin, die Anzahl der kommunizierten Bits zu minimieren. Ein Kommunikationsprotokoll, über das sich Alice und Bob, bevor sie die Eingabe erhalten, einigen, regelt den Ablauf der Kommunikation.