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.

Abgrenzung zur Komplexitätstheorie

Das Ziel der Komplexitätstheorie besteht darin, die Mindestressourcen zur Lösung von algorithmischen Problemen abzuschätzen. Die bisher bewiesenen unteren Schranken beruhen auf komplexitätstheoretischen Hypothesen oder beziehen sich auf spezielle Szenarien wie das Black-Box-Szenario.

→ Hauptartikel: Komplexitätstheorie

Die zum Beweis dieser unteren Schranken benutzten Kernideen wurden 1979 von Andrew C. Yao von der ursprünglich konkreten Anwendung der Komplexitätstheorie herausgefiltert und getrennt. Daraus entstand die Theorie der Kommunikationskomplexität. Zunächst als Kostenmaß für Datenaustausch bei parallelen Rechnern eingeführt, stellte sich die Kommunikationskomplexität in weiterer Folge als wichtiges Hilfsmittel zur Herleitung unterer Schranken beim VLSI Chip Design und der Schaltkreis-Komplexität heraus.

Aspekte und Grundprinzip

In der elektronischen Datenverarbeitung werden viele Aspekte als eine Abfolge von Kommunikationsprozessen betrachtet. Eine Kommunikation erfolgt immer dann bzw. ist immer dann notwendig, wenn zwei oder mehr Rechner, Komponenten, Systeme oder Menschen gemeinsam eine Aufgabe lösen müssen, die keiner von ihnen allein bewältigen kann, etwa weil keiner alleine über die gesamten Daten oder Ressourcen verfügt. In vielen Fällen ergibt sich eine offensichtliche Kommunikation wie z. B. wenn Informationen aus dem Internet gesucht werden. Dabei werden Anfragen und Antworten über eine Internetverbindung vermittelt.

Es sind aber auch Szenarien möglich, in welchen Kommunikation nur implizit stattfindet, wie z. B. durch Nutzen eines Computerprogrammes. In diesem Fall erfolgt die Kommunikation bzw. der Informationsaustausch zwischen unterschiedlichen Rechnerkomponenten.

Kommunikationsmodell

Bei der Berechnung einer Funktion auf einem VLSI-Chip, wird die gegebene Chipfläche in zwei Bereiche aufgeteilt. Dadurch erhält jeder Bereich einen Teil der Eingabe. Damit eine Berechnung der Funktion durchgeführt werden kann, müssen die beiden Bereiche des Chips Informationen austauschen. Wenn aufgrund der Eigenschaften der zu berechnenden Funktion viel Information ausgetauscht werden muss, benötigt man entweder viel Rechenzeit oder die Grenzlinie zwischen den beiden Bereichen des Chips und damit der Chip selber müssen groß sein.

Kommunikationskomplexität ist die Anzahl der Bits, die zwei Prozessoren (wir nennen diese Alice und Bob) austauschen müssen, um gemeinsam eine Funktion $F(x,y)$ auszuwerten, wenn ursprünglich jeder Prozessor eines der Argumente $x$ bzw. $y$ kennt.

Alice ist von der Eingabe $(x,y)$ nur $x$ bekannt, während Bob $y$ kennt. Beiden wird intern eine unbeschränkte Rechenkapazität gegeben. Der einzige wesentliche Aspekt ist die Kommunikation. Alice und Bob einigen sich vorab über ein Protokoll $P$, das für jede Situation vorschreibt, was zu tun ist.

Wenn $m$ die Folge der bereits kommunizierten Bits ist, dann kennt Alice $(x,m)$ und Bob $(y,m)$. Für beide muss nun klar sein, wer die nächste Nachricht sendet, wobei die gesendete Nachricht nur von lokalen Informationen abhängen darf. Am Ende der Kommunikation sollen Alice und Bob $F(x,y)$ kennen. Die Länge des Protokolls $P$, für die Eingabe $(x,y)$ ist die Anzahl von Bits, die zwischen Alice und Bob kommuniziert werden. Die Anzahl der zur Berechnung von $F(x,y)$ versendeten Bits wird dabei als die Kommunikationskomplexität des Protokolls $P$ bei Eingabe $(x,y)$ betrachtet.

Die Kommunikationskomplexität einer Funktion ist die Länge des kürzesten Protokolls.

AT² Schranken auf einem VLSI - Chip

Das Chip-Design wird heute wie damals davon bestimmt möglichst viel Logik auf einem kleinen Chip unterzubringen, dies reduziert die Kosten. Andererseits soll der Chip möglichst schnell ein Ergebnis berechnen. Für VLSI Designer waren daher untere Schranken in Bezug auf die Rechenzeit und die Größe des Chips von großem Interesse. Für die diskrete Fourier-Transformation konnte so z. B. bewiesen werden, dass AT² > n2 16 ist. Hierbei bezeichnet $A$ die Fläche des Chips, $T$ die benötigten Taktzyklen und $n$ die Länge der binären Eingabe. Durch diese Berechnung erhielt man die sogenannten AT² Schranken.

AT² Schranken sind nicht nur auf das VLSI Design beschränkt, sondern können auch für viele andere Funktionsberechnungen herangezogen werden.

Siehe auch

• Komplexitätstheorie
• Integrierter Schaltkreis (VLSI Chip)

Literatur

• E. Kushilevitz und N. Nisan - Communication Complexity - Cambridge University Press 1997 (Lehrbuch, 189 Seiten) - ISBN 0-521-56067-5
• N. Nisan und A. Wigderson - Rounds in Communication Complexity Revisited - SIAM Journal on Computing, Vol. 22 (1), Seiten 211–219, 19932

Weblinks

• Institut für Theoretische Informatik - Kommunikationskomplexität – englisch