Kommunikationskomplexität

Die Kommunikationskomplexität ist ein Teilgebiet der Komplexitätstheorie und wird angewendet um die Frage zu untersuchen, wie viel Kommunikation zum Lösen bestimmter Aufgaben nötig ist, wobei die Eingabe auf mehrere Rechner verteilt ist. Das Hauptaugenmerk liegt dabei auf der Anzahl der Bits, die zwischen den Rechnern versendet werden müssen, damit diese die ihnen gestellte Aufgabe erfüllen können. Die Kommunikationskomplexität ist ein Werkzeug der theoretischen Informatik, insbesondere beim Beweis von unteren Schranken für den Ressourcenbedarf von Berechnungen.