Direkt zum Inhalt

Lexikon der Mathematik: Kommunikationsspiel

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.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos