Eine Einladung in die Mathematik || Die Komplexität der Kommunikation

Die Komplexität der Kommunikation

Alexander A. Razborov

Zusammenfassung Als ich gebeten wurde, für dieses Buch einen Beitragüber etwas aus meinem Forschungsgebiet zu schreiben, musste ich sofortan Kommunikationskomplexität denken. Dieses trotz seiner Einfachheit sehrschöne und wichtige Teilgebiet der Komplexitätstheorie beschäftigt sich mitder Frage, wie viel Kommunikation zur Bestimmung eines bestimmten Er-gebnisses zwischen mehreren Beteiligten nötig ist. Wir werden das grund-legende Kommunikationsmodell einführen und einige klassische Ergebnisseangeben, teilweise sogar mit Beweis. Danach betrachten wir eine Variante,in der die Spieler gerechte Münzen werfen können. Wir schließen mit eini-gen anspruchsvolleren Modellen, über die man bis jetzt noch nicht allzu vielweiß. Alle Definitionen, Aussagen und Beweise sind komplett elementar, unddoch können wir offene Fragen angeben, die selbst die besten Forscher seitJahrzehnten nicht beantworten können.

1 Einleitung

Man sieht schon am Namen, dass sich Kommunikationskomplexität mit Mög-lichkeiten der Kommunikation zwischen mehreren Beteiligten beschäftigt,wobei schließlich alle das Erforderte wissen sollen, und wie man dies ameffizientesten, also mit geringster Komplexität erreicht. Sie ist ein kleiner,aber, wie wir noch sehen werden, sehr schöner und wichtiger Teil der Kom-plexitätstheorie, die wiederum genau auf der Grenze zwischen Mathematikund theoretischer Informatik liegt. Daher möchte ich zunächst einige Wör-

Alexander A. RazborovDepartment of Computer Science, The University of Chicago, 1100 East 58th Street, Chi-cago, IL 60637, USA; nd Steklov Mathematical Institute, Moskau, Russland, 117 966.E-mail: [email protected]

99

u

DOI 10.1007/978-3-642-25798-8_8, © Springer-Verlag Berlin Heidelberg 2013 D. Schleicher, M. Lackmann (Hrsg.), Eine Einladung in die Mathematik

100 Alexander A. Razborov

ter über Komplexitätstheorie und die in ihr untersuchten Probleme verlieren.Liest man lieber konkrete Mathematik als Philosophie, so kann man getrostdiese Einleitung überspringen und direkt zu Abschnitt 2 gehen.

Die meisten Probleme der Komplexitätstheorie folgen einem einfachenMuster: Wir wollen eine Aufgabe T erledigen. Meistens benutzen wir da-für einen oder mehrere Computer, aber dies ist für die Theorie nicht wichtig.Wir können unser Ziel auf viele verschiedene Weisen erreichen, und die Men-ge der Möglichkeiten sei PT . Je nach Kontext nennt man Elemente von PT

Algorithmen oder, wie in unserem Fall, Protokolle. Oft sieht man sofort, dasses zumindest einen Algorithmus oder ein Protokoll gibt, das T löst, weshalbPT nicht leer ist.

Obwohl alle P ∈ PT unsere Aufgabe T lösen, sind nicht alle Lösungengleichwertig. Einige sind besser als andere, da sie kürzer oder einfacher sind,weniger Ressourcen verbrauchen oder sich auf irgendeine andere Weise un-terscheiden. Die Hauptidee der Komplexitätstheorie ist nun, diese intuitivenVorlieben durch eine positive reellwertige Funktion μ : PT → R zu formali-sieren, die wir Komplexitätsmaß nennen. Hierbei soll eine Lösung P um sobesser sein, je kleiner μ(P ) ist. Ideal wäre es nun, die beste Lösung P ∈ PT

zu finden, also die, die μ(P ) minimiert. Meistens ist dies sehr schwer, weshalbForscher sich diesem Ideal von zwei Seiten zu nähern versuchen:

• Man versucht, „halbwegs gute“ Lösungen P ∈ PT zu finden, für die μ(P )zwar nicht minimal, aber doch „klein genug“ ist. Solche Ergebnisse nenntman „obere Schranken“, da wir aus mathematischer Sicht obere Schrankender Größe

minP∈PT

μ(P )

finden wollen, die (nicht gerade eine Überraschung!) die Komplexität derAufgabe T genannt wird.

• Man versucht untere Schranken zu finden: Für ein a ∈ R soll μ(P ) ≥ afür alle P gezeigt werden, es gibt also keine Lösung aus PT , die besserals a ist. Die Klasse PT ist oft sehr reichhaltig, und Lösungen P ∈ PT

können auf verschiedensten, oft unerwarteten Ideen aufbauen. Wir müs-sen ein einheitliches Argument für sie alle finden. Daher gehören Untere-Schranken-Probleme zu den schwersten der modernen Mathematik, undfür die überwältigende Mehrheit ist eine Lösung noch weit außer Sicht.

Nach all dieser Theorie ist es jetzt Zeit für ein paar Beispiele. Sogar ein-fache mathematische Rätsel drehen sich oft auf eine gewisse Weise um Kom-plexität, auch wenn man dies an der Formulierung selbst nicht sofort sieht.

Man hat 7 (oder 2010, . . . ) Münzen, von denen 3 (100, eine un-bekannte Zahl, . . . ) gefälscht und daher schwerer (leichter, einGramm schwerer, . . . ) als die anderen sind. Außerdem hat maneine Waage, auf der man beliebig viele (höchstens 10, . . . ) Münzenwiegen (vergleichen, . . . ) kann. Wie oft muss man wiegen, um alle(eine, . . . ) gefälschten Münzen zu finden?

Die Komplexität der Kommunikation 101

Dies sind typische Komplexitätsprobleme; sie hängen mit den sogenanntenSortiernetzwerken und -algorithmen zusammen. Die Aufgabe T ist das Fin-den gefälschter Münzen, und PT besteht aus allen Folgen von Wiegevorgän-gen, die einen dazu in die Lage versetzen. Das Komplexitätsmaß μ(P ) ist dieLänge von P (also die Anzahl der Wiegevorgänge).

Gegeben ist eine Zahl (Polynom, Ausdruck, . . . ). Wie viele Addi-tionen (Multiplikationen, . . . ) benötigt man, um sie aus gegebenenprimitiven Ausdrücken aufzubauen?

Dies ist nicht nur irgendein Komplexitätsproblem, sondern geradezu ein Mus-terbeispiel. Kannst du T,PT und μ für diesen Fall angeben? Übrigens irrtman sich im Glauben, dass die „Schulmultiplikation“ der nach Anzahl derZiffernoperationen optimale Algorithmus für das Finden des Produkts zwei-er ganzer Zahlen ist. In den Arbeiten von Karatsuba [13], Toom und Cook(1966), Schönhage und Strassen [26] und Fürer [11] wurde sie wieder undwieder verbessert, und wir wissen immer noch nicht, ob Fürers Algorithmusoptimal ist. Diese fortgeschrittenen Algorithmen sind aber auch nur für sehrgroße Zahlen (tausende von Stellen lang) schneller als die „Schulmethode“.

Die berühmte Frage „P vs. NP“ ist ein weiteres Komplexitätsproblem(falls dieser Begriff dir nichts sagt, kann ich http://www.claymath.org/millennium/P_vs_NP empfehlen). Die Aufgabe T ist hierbei die Lösung einesbestimmtenNP-vollständigen Problems, z. B. SATISFIABILITY, und PT istdie Klasse aller diese Aufgabe erledigenden Algorithmen.

In diesem Beitrag beschäftigen wir uns mit Komplexitätsproblemen derKommunikation. Das Modell ist sehr hübsch und leicht zu erklären, führtaber schnell zu interessanten Fragen, die seit Jahrzehnten offen sind. . . Au-ßerdem durchdringen Ideen und Methoden der Kommunikationskomplexi-tätstheorie heutzutage nahezu alle Bereiche der Komplexitätstheorie, auchwenn wir hierauf nicht näher eingehen können.

Fast alles, das in diesem Beitrag behandelt wird (und noch vieles mehr)lässt sich im klassischen Buch [17] finden. Im kürzlich erschienenen Lehrbuch[3] über Komplexitätstheorie geht Kapitel 13 ausschließlich um Kommunika-tionskomplexitätstheorie, und man kann über das ganze Buch verstreut ihreAnwendungen finden.

Da wir in diesem Text recht viel Notation einführen, wird diese am Endedes Beitrags nochmals geschlossen mit einer kurzen Beschreibung aufgeführt.

2 Das Grundmodell

Yao führte das grundlegende (deterministische) Modell in seiner bahnbre-chenden Arbeit [27] ein. Es gibt zwei Spieler, die nach Tradition Alice undBob heißen (s. a. die folgende Anmerkung), endliche Mengen X,Y und eineFunktion f : X × Y −→ {0, 1}. Alice und Bob stehen nun vor der Aufgabe,


f(x, y) für einen gegebenen Wert (x, y) zu berechnen. Interessant wird diesdadurch, dass Alice nur den ersten Teil x ∈ X und Bob nur den zweiten Teily ∈ Y des Werts kennt. Sie besitzen zwar einen in beide Richtungen laufendenKommunikationskanal, aber diesen sollte man sich wie eine transatlantischeTelefonverbindung oder ein Funkgerät mit einem Raumschiff am Mars vor-stellen. Jede Kommunikation ist teuer, und daher wollen Alice und Bob dieAnzahl der für die Berechnung von f(x, y) ausgetauschten Bits minimieren.

Ein Protokoll P ∈ PT sieht also wie folgt aus (siehe Abbildung 1). Alice

Abb. 1. Ein Protokoll P zur Berechnung von f(x, y). (Bild von Alice von John Tenniel.)

schickt eine Nachricht, die der Einfachheit halber als Binärwort a1 (d. h. alsFolge von Einsen und Nullen) übermittelt wird. Bob antwortet mit b1, dasnur von seinem Wert y und Alices Nachricht a1 abhängt. Beide fahren aufdiese Weise fort, bis einer von ihnen (sagen wir Bob) f(x, y) berechnen kannund Alice diesen Wert in der t-ten Runde übermittelt.

Anmerkung 1. Alice und Bob sind wohl die liebenswürdigsten und bekanntes-ten Helden der gesamten Literatur über Komplexitätstheorie oder Kryptogra-phie, einem eng verwandten Feld. Daher werden wir sie in dieser Geschichtenoch oft wiedertreffen, und genau wie sonst haben sie immer recht viel zutun. Manchmal wollen sie nur teilweise das Gleiche erreichen und geben sichviel Mühe, keine überflüssigen Informationen zu verraten; dies nennt manKryptographie. Oft gibt es einen bösen Lauscher (aus offensichlichen Grün-den Eve genannt). Manchmal können sich Alice und Bob nicht einmal sichersein, dass ihr Gegenüber wirklich das Protokoll befolgt, wobei sie sich in die-sem Fall aber normalerweise Arthur und Merlin nennen. In unserem Beitragbeschränken wir uns aber auf die einfachste Möglichkeit: komplettes gegensei-tiges Vertrauen, keine Geheimnisse und ein sicherer Kommunikationskanal.

In dieser Definition haben wir einige Dinge absichtlich nicht genau fest-gelegt. Ist etwa die Länge von Alices Nachricht a1 fest, oder darf sie von xabhängen? Kann analog die Anzahl der Runden t von x und y abhängen, undwenn ja, wie weiß Alice, dass Bobs Nachricht bt wirklich die letzte ist und


f(x, y) enthält? Es stellt sich jedoch heraus, dass all diese Details kaum einenEinfluss haben, weswegen der Leser sie nach Belieben festlegen möge — dieKomplexität ändert sich dadurch nur um einen kleinen additiven Faktor.

Wie misst man nun die Komplexität μ(P ) eines Protokolls P? Es gibt eini-ge vernünftige Definitionen. In unserem Beitrag beschränken wir uns auf diewichtigste und beliebteste, die Komplexität des schlimmsten Falls heißt. Füreinen festen Wert (x, y) ∈ X×Y seien die Kosten des Protokolls P für diesenWert die Gesamtanzahl1 |a1|+|b1|+. . .+|bt| der für diesen Wert ausgetausch-ten Bits (s. a. Abbildung 1). Die Komplexität (aus historischen Gründen auchKosten genannt) cost(P ) des Protokolls P seien nun die maximalen Kostenvon P für einen beliebigen Wert (x, y) ∈ X×Y . Schließlich sei die Kommuni-kationskomplexität C(f) der (Berechnung der) Funktion f : X×Y −→ {0, 1}das Minimum minP∈Pf

cost(P ) über alle korrekten, d. h. für alle (x, y) denrichtigen Wert f(x, y) ergebenden Protokolle P . Wir würden nun gerne C(f)für „interessante“ Funktionen f ausrechnen oder zumindest gut abschätzen.

Man sieht sofortC(f) ≤ �log2 |X |�+ 1 (1)

für jedes Problem2 f . Das diese Kosten ergebende Protokoll ist sehr leicht:Alice verschlüsselt ihren Wert x mit einer injektiven Kodierung f1 : X −→{0, 1}log2 |X|� als Binärwort der Länge �log2 |X |� und schickt Bob a1 = f1(x).Dieser entschlüsselt die Nachricht (wir nehmen an, dass sich beide vor-her auf eine Kodierung f1 geeinigt haben!) und schickt Alice die Antwortf(f−1

1 (a1), y) zurück.Überraschenderweise können wir in unserem Modell nur für wenige inter-

essante Funktionen f ein deutlich besseres Protokoll als (1) angeben. Hier istein zugegebenermaßen triviales Beispiel. Es seien X und Y die natürlichenZahlen, die nicht größer als eine feste Zahl N sind: X = Y = {1, 2, . . . , N}.Alice und Bob wollen nun die {0, 1}-wertige Funktion fN (x, y) berechnen, diegenau dann 1 ausgibt, wenn x+y durch 2010 teilbar ist. Alice spart nun viel,wenn sie Bob nicht den gesamten Wert x, sondern nur den Rest x mod 2010schickt. Offensichtlich kann Bob damit x+y mod 2010 (und damit fN (x, y))berechnen, und die Kosten dieses Protokoll sind nur �log2 2010�+ 1 (= 12).Also

C(fN ) ≤ �log2 2010�+ 1 . (2)

Nun sind Komplexitätstheoretiker faul und nicht sehr gut in Grundschul-arithmetik. Für sie ist das Besondere an der rechten Seite von (2), dass sieirgendeine Konstante ist, die wie durch Magie nicht von der Größe der Werteabhängt. Statt den Wert also wirklich auszurechnen, würden wir lieber dieseTatsache betonen und bedienen uns dafür der mathematischen großes-O-

1 |a| ist die Länge des Binärworts a.2 Hierbei sollte man beachten, dass Komplexitätstheoretiker eine Funktion f gerne mitdem von ihr dargestellten Berechnungsproblem identifizieren. So betrachtet man die nochzu definierende Gleichheitsfunktion EQN auch als Problem, die Gleichheit zweier Wörterzu überprüfen.


Schreibweise. In dieser ist (2) zwar schwächer, aber dafür noch einfacher:

C(fN ) ≤ O(1) .

Es gibt also eine positive universelle Konstante K, deren Wert man (nor-malerweise) auch explizit berechnen kann, so dass für alle N die Unglei-chung C(fN ) ≤ K · 1 = K gilt. Analog bedeutet C(fN ) ≤ O(log2 N) geradeC(fN ) ≤ K log2 N usw. Im Laufe unseres Beitrags werden wir diese Stan-dardnotation3 noch ausführlich benutzen.

Wir betrachten nun ein einfacheres Problem, das so elementar wie nurmöglich aussieht. Seien X = Y gleiche Mengen der Größe N . Wir können unswieder auf {1, 2, . . . , N} beschränken, aber in diesem Fall ist dies unwichtig.Die Gleichheitsfunktion EQN ist so definiert, dass EQN (x, y) = 1 ⇐⇒ x =y. Anders gesagt wollen Alice und Bob überprüfen, ob sie die gleiche Datei,Datenbank usw. haben, was natürlich für alle Anwendungen sehr wichtig ist.

Wir erhalten natürlich sofort die triviale Schranke (1), falls Alice einfachihren gesamten Wert x an Bob schickt. Aber können wir im Vergleich zudiesem trivialen Protokoll noch irgendetwas sparen? Ich empfehle dem Leser,jetzt das Buch eine Weile zur Seite zu legen und sich selbst einige Gedankenhierzu zu machen. Nur so kann man das Folgende wirklich würdigen.

3 Der Leser sei gewarnt, dass man diese Notation in den meisten Texten mit Gleichheits-statt Ungleichheitszeichen sieht, d. h. im vorherigen Beispiel C(fN ) = O(log2 N). Wirdenken aber, dass diese Konvention einige Probleme verursacht und insbesondere in kom-plizierten Fällen unhandlich und wenig mitteilsam wird.



3 Untere Schranken

Hattest du Erfolg? Du musst dir keine Sorgen machen, wenn du keine zu-sätzlichen Sparmöglichkeiten finden konntest, da man mittlerweile weiß, dassdie Schranke (1) nicht verbessert werden kann: jedes Protokoll für EQN hatmindestens Kosten log2 N . Auch dies wurde in Yaos bahnbrechender Arbeit[27] bewiesen, und die hierfür benutzten Ideen sollten die Entwicklung derKommunikationskomplexitätstheorie auf Jahrzehnte hinaus bestimmen. DerBeweis selbst ist nicht sehr schwer, aber sehr lehrreich:

Gegeben sei ein Protokoll P , wie es in Abbildung 1 gezeigt ist. Wir wis-sen, dass Bob durch Ausführen dieses Protokolls EQN (x, y) erfüllt. Hierausmüssen wir nun irgendwie cost(P ) ≥ log2 N folgern.

Neulinge im Gebiet der unteren Schranken machen oft den Fehler, P „rich-tiges“ Verhalten vorzuschreiben, das heißt bewusst oder unbewusst Annah-men über das beste Protokoll P aus dem gesunden Menschenverstand abzu-leiten. In unserer Situation könnte man etwa mit „Sei i das erste Bit in derBinärdarstellung von x und y, das von P verglichen wird“ anfangen. Solche„Argumente“ führen aber auf den Holzweg, da das beste Protokoll gar nichtso oder auf irgendeine andere von uns als „intelligent“ bezeichnete Art vor-gehen muss. Die Komplexitätstheorie kennt viele geniale Algorithmen undProtokolle, die bis zum letzten Schritt seltsame, scheinbar irrelevante Resul-tate ausrechnen und die Antwort erst im Abschluss wie ein Kaninchen auseinem Zylinder ziehen — ein gutes Beispiel sehen wir noch. Das Schöne undVerzwickte an der Komplexitätstheorie ist nun, dass wir auch alle Protokolle,die (unserer Meinung nach) irrational vorgehen, berücksichtigen müssen, undin unserem Fall dürfen wir nichts als das in Abbildung 1 Gezeigte über dasProtokoll P annehmen.

Nach diesen warnenden Worten wollen wir nun Yaos Spuren folgen undsehen, wie viel Nützliches wir noch nur aus Abbildung 1 ableiten können.Obwohl wir uns im Moment nur für f = EQN interessieren, lässt sich YaosArgumentation auf jede Funktion f anwenden. Sei also für den Moment feine beliebige Funktion, deren Kommunikationskomplexität wir abschätzenwollen; in Korollar 2 kehren wir zu EQN zurück.

Zunächst führen wir das unheimlich nützliche Konzept der Geschichte oderNiederschrift ein: Dies ist die Folge (a1, b1, . . . , at, bt) der während der Durch-führung des Protokolls von Alice und Bob ausgetauschten Nachrichten. Diesessehr allgemeine Konzept trifft man oft, auch außerhalb der Kommunikations-komplexitätstheorie, an.

Wir sehen nun, dass es höchstens 2cost(P ) verschiedene Geschichten gebenkann, da es nur so viele verschiedeneWörter4 der Länge cost(P ) gibt. Für jedeGeschichte h können wir die Menge Rh der zu dieser Geschichte führenden

4 In Abhängigkeit von den genauen Details des Modells können die Geschichten verschie-dene Längen haben, von der Kommasetzung abhängen usw., wodurch sich diese Zahl leichterhöhen kann. Wir sind aber faul und ignorieren kleine additive oder multiplikative Fak-toren.


Werte (x, y) bilden. In diesen Mengen stecken bereits viele Informationenüber das Protokoll.

Zunächst führt jeder Wert (x, y) zu genau einer Geschichte. Also ist dieFamilie {Rh} eine Partition oder disjunkte Überlagerung der Menge allerWerte X × Y :

X × Y =⋃̇

h∈HRh , (3)

wobei H die Menge aller möglichen Geschichten ist. Das Zeichen⋃̇

steht fürdisjunkte Vereinigung und teilt uns zwei verschiedene Sachen mit: EinerseitsX × Y =

⋃h∈H Rh, andererseits Rh ∩Rh′ = ∅ für verschiedene h �= h′ ∈ H.

Es enthält nun jede Geschichte h den Wert der Funktion f(x, y) als Bobsletzte Nachricht bt. Also ist jedes Rh eine f -monochromatische Menge, alsoentweder f(x, y) = 0 für alle (x, y) ∈ Rh oder f(x, y) = 1 für alle solche(x, y).

Zuletzt, und das ist der springende Punkt, ist jedes Rh ein (kombina-torisches) Rechteck — es hat die Form Rh = Xh × Yh für bestimmteXh ⊆ X, Yh ⊆ Y . Dies folgt direkt aus dem Satz „(x, y) führt zur Geschichte(a1, b1, . . . , at, bt)“. Schauen wir uns nämlich Abbildung 1 genau an, so sehenwir, dass dies zu den folgenden „Zwangsbedingungen“ für (x, y) äquivalentist: f1(x) = a1, g1(y, a1) = b1, f2(x, a1, b1) = a2, . . . , gt(y, a1, . . . , at) = bt.Hierbei hängen die Bedingungen, die an einer ungeraden Stelle in dieser Ket-te stehen, nur von x ab (da h fest ist!); sei Xh die Menge der x ∈ X , dieall diese Bedingungen erfüllen. Analog sei Yh die Menge der y ∈ Y , die diean geraden Stellen stehenden Bedingungen erfüllen. Wie man leicht sieht, istRh = Xh × Yh!

Es ist nun Zeit für eine kurze Zusammenfassung. Für jedes Protokoll P ,das unser Problem f : X × Y −→ {0, 1} löst, konnten wir X × Y in höchs-tens 2cost(P ) Stücke so aufspalten, dass jedes Stück ein f -monochromatischeskombinatorisches Rechteck ist. Wir bezeichnen mit χ(f) die kleinste An-zahl f -monochromatischer Rechtecke, in die wir X×Y partitionieren können(Komplexitätstheoretiker lieben es wirklich, neue Komplexitätsmaße einzu-führen). Wir haben somit bis auf eine kleine, von den Details des Modellsabhängende multiplikative Konstante gezeigt:

Theorem 1 (Yao). C(f) ≥ log2 χ(f). �Nun kehren wir wieder zum Spezialfall f = EQN zurück. Jedes f -

monochromatische kombinatorische Rechteck ist entweder ein 0-Rechteck(d. h. eines, auf dem f verschwindet) oder ein 1-Rechteck. Die Funktion EQN

hat viele große 0-Rechtecke. (Kannst du eins finden?) Aber alle 1-Rechteckesind sehr primitiv: jedes solche Rechteck besteht nur aus einem Punkt (x, x).Nur für das Überdecken der „Diagonale“ {(x, x) | x ∈ X } benötigt man alsobereits N verschiedene 1-Rechtecke, woraus χ(EQN ) ≥ N folgt. Mit Theo-rem 1 ergibt das das gewünschte Ergebnis:

Korollar 2. C(EQN ) ≥ log2 N . �


Übung 1. Die Funktion LEN (kleinergleich) ist auf {1, 2, . . . , N}×{1, 2, . . . , N}durch

LEN (x, y) = 1 genau dann, wenn x ≤ y

definiert. Zeige C(LEN ) ≥ log2 N .

Übung 2 (schwer). Die Funktion DISJn ist auf {0, 1}n × {0, 1}n durch

DISJn(x, y) = 1 genau dann, wenn ∀i ≤ n : xi = 0 ∨ yi = 0 ,

definiert, ist also genau dann 1, wenn die Mengen der Positionen, an denenx und y eine 1 haben, disjunkt sind. Man zeige C(DISJn) ≥ Ω(n).

(Hierbei ist Ω eine weitere Lieblingsnotation der Komplexitätstheoretiker.Sie ist dual zu dem „großen O“; die Ungleichung C(DISJn) ≥ Ω(n) bedeutet,dass es eine Konstante ε > 0, die wir nicht berechnen wollen, gibt, so dassC(DISJn) ≥ εn für alle n.)

Hinweis. Wie viele Punkte (x, y) mit DISJn(x, y) = 1 gibt es? Und was istdie maximale Größe eines 1-Rechtecks?

4 Sind die Schranken scharf?

Wir interessieren uns nun dafür, wie gut die Aussage von Theorem 1 imAllgemeinen ist. Kann χ(f) klein sein, so dass es eine gute disjunkte Überla-gerung durch f -monochromatische Rechtecke gibt, und C(f) trotzdem großsein, was insbesondere besagt, dass wir aus unserer Überlagerung kein ordent-liches Kommunikationsprotokoll konstruieren können? Abbildung 2 deutet

Abb. 2. Was soll Alice machen?

bereits an, dass diese Frage durchaus nichttrivial sein kann: sie zeigt ein Bei-spiel für eine disjunkte Überlagerung durch nur fünf Rechtecke, die keinemKommunikationsprotokoll entspricht.

Wie so oft hängt die Antwort von der verlangten Genauigkeit ab. In dernächsten einflussreichen Arbeit zur Kommunikationskomplexität [1] wurdeunter anderem gezeigt


Theorem 3 (Aho, Ullman, Yannakakis). C(f) ≤ O(log2 χ(f))2.

Der Beweis ist zwar nicht schwer, aber trotzdem höchstgradig nichttrivial.Man mag versuchen, ihn selbst zu finden, oder ihn z. B. in [17] nachlesen.

Benötigen wir das Quadrat in Theorem 3? In den fast dreißig Jahren seitdem Erscheinen von [1] haben viele Leute diese Frage von beiden Seitenangegangen. Bis jetzt hat sie allen Bemühungen widerstanden. . .

Offenes Problem 1. Ist stets C(f) ≤ O(log2 χ(f))?

Neben Theorem 3 enthält [1] viele weitere wichtige Ergebnisse über soge-nannte nichtdeterministische Kommunikationskomplexität. In diesem Modellerhalten Alice und Bob zusätzlich ein gemeinsames Wort z, das nicht vomProtokoll festgelegt wird (daher auch der Name), sondern ihnen von einerallmächtigen dritten Partei gegeben wird, die sie von f(x, y) = 1 überzeugenwill. Wir fordern dabei, dass ein solches überzeugendes Wort z genau dannexistiert, wenn f(x, y) wirklich 1 ist. Hierbei wird also die Symmetrie zwi-schen den Antworten 0 und 1 gebrochen. Aus Platzgründen können wir nurkurz auf dieses wichtige Konzept eingehen, und die hier erwähnten Komple-xitätsmaße werden im späteren Beitrag kaum verwendet werden.

Es sei t(f) wie χ(f) definiert, mit dem Unterschied, dass sich die mono-chromatischen Rechtecke der Überlagerung schneiden dürfen. Offensichtlicht(f) ≤ χ(f), aber Theorem 3 gilt immer noch: C(f) ≤ O(log2 t(f))

2. An-dererseits gibt es Beispiele, in denen C(f) Größenordnung (log2 t(f))

2 hat.Die (negative) Antwort auf Problem 1 ist im Fall nicht notwendigerweisedisjunkter Überlagerungen also bekannt.

Es seien nun χ0(f) und χ1(f) wie χ(f) definiert, wobei wir uns aber nurfür Überlagerungen der 0 bzw. 1 ergebenden Werte interessieren; offensicht-lich χ(f) = χ0(f)+χ1(f). Es gilt immer noch C(f) ≤ O(log2 χ1(f))

2 und ausSymmetriegründen C(f) ≤ O(log2 χ0(f))

2. Analog definieren wir die Größent0(f) und t1(f) (die oben erwähnte nichtdeterministische Kommunikations-komplexität stellt sich als log2 t1(f) heraus). Wir können nur aus log2 t1(f)oder log2 t0(f) keine vernünftige (etwa besser als exponentielle) Schranke fürC(f) ableiten: So ist etwa t0(EQN ) ≤ O(log2 N) (warum?), aber bekannt-lich C(EQN ) ≥ log2 N . Zusammengefasst können wir die deterministischeKommunikationskomplexität nicht gut durch die nichtdeterministische ab-schätzen; dies wird aber möglich, wenn die nichtdeterministische Kommuni-kationskomplexität der negierten Funktion auch klein ist.

Der nächste Meilenstein wurde in der Arbeit [19] gesetzt, die algebraischeMethoden in das Feld einführte. Bis jetzt basierten alle unteren Schranken(Korollar 2 sowie Übungen 1 und 2) für χ(f) auf derselben naiven Idee: Manwählt „viele“ Werte D ⊆ X × Y , so dass ein f -monochromatisches Rechtecknur „wenige“ von ihnen überdecken kann und wendet dann das Schubfach-prinzip an. Hierbei benutzen wir aber nicht die Disjunktheit der Überlage-rung (3), schätzen also eigentlich nur t(f) und nicht χ(f) ab. Ist das gutoder schlecht? Dies hängt immer vom Standpunkt ab. Einerseits ist es natür-lich praktisch, automatisch untere Schranken für die nichtdeterministische


Kommunikationskomplexität log2 t1(f) mitzubeweisen. Andererseits ist diet(f) entsprechende Größe manchmal immer klein, und um χ(f) von untenabzuschätzen, müssen wir also Methoden benutzen, die den Unterschied zwi-schen beiden Begriffen „fühlen“. Die erste solche Methode war Mehlhorns undSchmidts untere-Rang-Schranke [19].

Für diese benötigen wir grundlegende Begriffe aus der linearen Algebrawie Matrizen M oder ihren Rang rg(M) sowie einige ihrer einfachsten Eigen-schaften. Für den Leser, der diese Begriffe nicht kennt, bietet sich jetzt dieeinmalige Gelegenheit, sich ein Buch über Lineare Algebra zu greifen und ei-nige Kapitel zu lesen. Früher oder später muss man diese sowieso lernen, aberjetzt kann man außerdem noch eine unerwartete und interessante Anwendungdieser Abstrakta sehen.

Sei f : X × Y −→ {0, 1} beliebig. Wir können ihre Werte in der Kommu-nikationsmatrix Mf anordnen. Diese hat für jedes Element von X eine Zeileund für jedes Element von Y eine Spalte (die Reihenfolge ist dabei jeweilsirrelevant), und in die Zelle in der x-ten Zeile und y-ten Spalte schreiben wirf(x, y). Eine Verbindung zwischen diesen verschiedenen Welten Kombinato-rik und Lineare Algebra liefert uns der nächste Satz:

Theorem 4. χ(f) ≥ rg(Mf ).

Beweis. Der Beweis ist bemerkenswert einfach. Seien R1, . . . , Rχ disjunk-te 1-Rechtecke, die alle (x, y) mit f(x, y) = 1 überdecken, mit χ ≤ χ(f).Sei fi : X × Y −→ {0, 1} die charakteristische Funktion des RechtecksRi, also fi(x, y) = 1 ⇐⇒ (x, y) ∈ Ri, und sei Mi = Mfi ihre Kom-munikationsmatrix. Dann rg(Mi) = 1 (warum?) und Mf =

∑χi=1 Mi. Also

rg(Mf) ≤∑χ

i=1 rg(Mi) ≤ χ ≤ χ(f). �Man sieht den Nutzen von Theorem 4 bereits daran, dass MEQN

dieEinheitsmatrix ist (falls wir die Zeilen und Spalten gleich anordnen), alsorg(MEQN

) = N und damit folgt sofort Korollar 2. Analog ist MLENdie obe-

re Dreiecksmatrix und daher rg(MLEN ) = N . Wir erhalten Übung 1. Mitmehr Aufwand erhält man auch, dass die Kommunikationsmatrix MDISJn

nichtsingulär ist, also rg(MDISJn) = 2n. Es folgt C(DISJn) ≥ n, was wir auf-

grund von (1) nicht mehr groß verbessern können, und was auch stärker alsdas kombinatorische Ergebnis in Übung 2 ist (das Ω ist verschwunden).

Wie scharf ist die Schranke in Satz 4? Eine Weile lang vermutete manχ(f) ≤ (rg(Mf ))

O(1) oder vielleicht sogar χ(f) ≤ O(rg(Mf )). In dieser Formwurde die Vermutung in mehreren Arbeiten [2, 23, 21] widerlegt. Aber es istimmer noch möglich und glaubhaft, dass

χ(f) ≤ 2O(log2 rg(Mf ))2

;

mit Theorem 3 ergibt dies immer noch die höchstgradig nichttriviale Unglei-chung C(f) ≤ O(log2 rg(Mf ))

4.


Trotz jahrzehntelanger Forschung können wir diese Frage immer noch nichtbeantworten, und es haben sich noch nicht einmal gute Ansätze für dieses ineinschlägigen Kreisen als Log-Rang-Vermutung bekannte Problem ergeben.

Offenes Problem 2 (Log-Rang-Vermutung). Gilt stets

χ(f) ≤ 2(log2 rg(Mf ))O(1)

?

Äquivalent dazu (nach den Sätzen 1 und 3), ist stets C(f) ≤ (log2 rg(Mf ))O(1)?

5 Probabilistische Modelle

Hiermit verlassen wir das grundlegende Modell der Kommunikationskom-plexität. Mit einigen Veränderungen entstehen noch mehr faszinierende undschwere Probleme. Eine der wichtigsten, die wir als einzige noch ausreichendbehandeln können, ist das Modell der probabilistischen Kommunikationskom-plexität.

Alice und Bob nehmen sich jetzt weniger vor und tolerieren bei der Be-rechnung von f(x, y) auch bis zu einer gewissen Wahrscheinlichkeit Fehler.Beide besitzen eine gerechte Münze (im wissenschaftlichen Jargon ein zufäl-liger Bit-Erzeuger), die sie während der Durchführung des Protokolls werfenund je nach Ergebnis ihre Nachrichten anpassen. Alles andere bleibt gleich(also wie in Abbildung 1), aber wir müssen zunächst noch definieren, wannein Protokoll P eine Funktion f richtig berechnet.

Sei ein Wert (x, y) festgelegt. Alice und Bob mögen ihre Münzen insgesamtr Mal werfen, womit wir 2r mögliche Ergebnisse erhalten. Manche sind gut,d. h. Bob berechnet den richtigen Wert f(x, y), in anderen, schlechten Fällenirrt er sich. Ist nun Gut(x, y) die Menge aller guten Ergebnisse, so heißt dieGröße

pxy =|Gut(x, y)|

2r(4)

aus naheliegenden Gründen Erfolgswahrscheinlichkeit für den Wert (x, y).Welche Bedingungen stellen wir nun an diese Größe? Es gibt ein sehr

einfaches Protokoll mit Kosten 1, das pxy = 1/2 liefert: Bob wirft einfachseine Münze und behauptet, dass das Ergebnis f(x, y) ist. Wir verlangenalso zumindest

pxy > 1/2 . (5)

Sollten wir die Erfolgswahrscheinlichkeit noch mehr von 1/2 trennen?Wie sich herausstellt, gibt es im Grunde genommen nur drei Möglichkeiten

(wir bleiben faul und kümmern uns nicht um die genauen Werte von Kon-stanten). Die beliebteste und wichtigste ist, pxy ≥ 2/3 für alle Werte (x, y)zu fordern. Die minimalen Kosten eines diese Bedingung erfüllenden pro-


babilistischen Protokolls nennt man fehlerbeschränkte probabilistische Kom-munikationskomplexität der Funktion f , und man bezeichnet sie mit R(f).Fordern wir nur für jeden Wert (x, y), dass (5) gilt, so nennen wir das Modellfehlerunbeschränkt, und das entsprechende Komplexitätsmaß heißt U(f). Imdritten Modell (weniger bekannt und hier nicht betrachtet) fordern wir auch(5), lassen aber die Anzahl der Münzwürfe in die Kosten einfließen. Man er-hält etwa, dass aus (5) für jedes Protokoll mit Kosten O(log2 n) bereits diebessere Schranke px,y ≥ 1

2 + 1p(n) für ein bestimmtes Polynom p(n) folgt.

Wir forderten in der Definition von R(f) nur pxy ≥ 2/3 und nicht etwapxy ≥ 0.9999, da wir mit der sogenannten Amplifikation zeigen können, dassbeide Bedingungen mehr oder weniger äquivalent sind. Haben Alice und Bobnämlich erst einmal ein Protokoll mit Kosten R(f), das pxy ≥ 2/3 erfüllt, sokönnen sie es tausendmal hintereinander ausführen und am Ende die häufigsteAntwort ausgeben. Dann ist die Fehlerwahrscheinlichkeit dieses Protokollsmit Kosten ≤ 1000R(f) höchstens 10−10. . . (für den Beweis benötigt man einwenig elementare Stochastik, etwa die Chernoff-Ungleichung).

Helfen uns diese Münzen nun wirklich, gibt es also interessante Probleme,die sich mit Zufall effizienter als ohne lösen lassen? Diese Frage wird von derfolgenden schönen Konstruktion von Rabin und Yao beantwortet, die manmit Korollar 2 vergleichen sollte:

Theorem 5. R(EQN ) ≤ O(log2 log2 N).

Beweis. Für den Beweis stellen wir Elemente von X und Y als Binärwör-ter der Länge n = �log2 N� dar. Hierbei interpretieren wir das Binärwortx1x2 . . . xn als Polynom x1 + x2ξ + . . . + xnξ

n−1 in einer Variable ξ. Aliceund Bob haben also zwei Polynome der obigen Form, die sie auf Gleich-heit überprüfen wollen. Hierfür einigen sie sich im Voraus auf eine Primzahlp ∈ [3n, 6n] (die nach dem Bertrandschen Postulat stets existiert). DurchMünzwurf bestimmt Alice ein zufälliges Element ξ ∈ {0, 1, . . . , p − 1}, be-stimmt den Rest (!) g(ξ) mod p und schickt Bob das Paar (ξ, g(ξ) mod p).Bob bestimmt h(ξ) mod p und berechnet genau dann 1, wenn h(ξ) = g(ξ)mod p.

Wie verlangt hat dieses Protokoll nur Kosten O(log2 n), da man dies dieAnzahl von Bits ist, die man zur Übertragung des Paares (ξ, g(ξ) mod p)zweier durch p ≤ O(n) beschränkten ganzen Zahlen benötigt. Was ist aberseine Erfolgswahrscheinlichkeit? Für EQ(g, h) = 1 ist g = h, und Bob gibtstets eine 1 aus, weshalb es in diesem Fall nie einen Fehler gibt. Was pas-siert aber für g �= h? Dann ist (h − g) ein von Null verschiedenes Polynomvom Grad ≤ n. Jedes solche Polynom kann über dem endlichen Körper Fp

höchstens n verschiedene Nullstellen haben. Dies heißt einfach nur, dass dieAnzahl der schlechten ξ ∈ {0, 1, . . . , p − 1}, für die Bob sich aufgrund vong(ξ) = h(ξ) mod p in die Irre führen lässt, durch n ≤ p

3 beschränkt ist. Da ξzufällig aus {0, 1 . . . , p− 1} gewählt wurde, ist die Erfolgswahrscheinlichkeitmindestens 2/3. �


Auch die anderen bereits gesehenen Probleme lassen sich für probabilisti-sche Protokolle untersuchen. Die Kleinergleich-Funktion aus Übung 1 verän-dert ihr Verhalten auch: R(LEN ) ≤ O(log2 log2 N), wobei hierfür der Beweisunheimlich viel komplizierter ist [17, Exercise 3.18]. Für die Disjunktheits-funktion hilft uns der Zufall nicht viel:

Theorem 6. R(DISJn) ≥ Ω(n).

Auch diesen Beweis können wir hier nicht geben. Stattdessen untersuchenwir eine andere wichtige Funktion, das Skalarprodukt mod 2, die wir nunbeschreiben.

Betrachte für x, y ∈ {0, 1}n wie für Disjunktheit die Menge der Indizes imit xi = yi = 1. Dann ist IPn(x, y) = 1 genau dann, wenn die Mächtigkeitdieser Menge ungerade ist. Chor und Goldreich [9] bewiesen

Theorem 7. R(IPn) ≥ Ω(n).

Auch hier können wir den vollständigen Beweis nicht geben, wollen abertrotzdem den ihn durchziehenden roten Faden aufzeigen.

Bis jetzt haben wir uns nur für f -monochromatische Rechtecke, also sol-che, die entweder nur aus Nullen oder nur aus Einsen bestehen, interessiert.Dabei wollten wir zeigen, dass jedes solche Rechteck in einem bestimmtenSinne klein ist. Für allgemeine probabilistische Protokolle müssen wir nunauch allgemeine Rechtecke R betrachten. Jedes solche Rechteck enthält einegewisse Anzahl N0(f,R) von Punkten mit f(x, y) = 0 und N1(f,R) Punktemit f(x, y) = 1. Wir müssen nun zeigen, dass auch „große“ R „ausgeglichen“sind, womit wir meinen, dass N0(f,R) und N1(f,R) „nah beieinander“ lie-gen. Mathematisch definieren wir die Diskrepanz unter Gleichverteilung5 derFunktion f : X × Y −→ {0, 1} als

Discu(f) = maxR

|N0(f,R)−N1(f,R)||X | × |Y | ,

wobei sich das Maximum über alle möglichen kombinatorischen RechteckeR ⊆ X × Y erstreckt.

Es stellt sich nun heraus, dass

R(f) ≥ Ω(log2(1/Discu(f))) , (6)

also gibt uns geringe Diskrepanz gute Abschätzungen für probabilistischeProtokolle. Theorem 7 lässt sich nun mit Discu(IPn) ≤ 2−n/2, was bereitsrecht nichttrivial ist, beweisen.

Was passiert nun, wenn wir zusätzlich probabilistische Protokolle mit un-beschränktem Fehler zulassen, also nur fordern, dass die Erfolgswahrschein-lichkeit (4) stets echt größer als 1/2 ist? Die Komplexität der Gleichheits-funktion entartet vollkommen [20]:

5 Man kann dies auch auf andere Verteilungen verallgemeinern.


Theorem 8. U(EQN ) ≤ 2.

Auch die Disjunktheitsfunktion wird einfacher, und dies ist eine gute Übung:

Übung 3. Man zeige U(DISJn) ≤ O(log2 n).

Das innere Produkt hält aber die Stellung:

Theorem 9. U(IPn) ≥ Ω(n).

Dieses so schöne wie geniale Ergebnis Forsters [10] gehört zu meinen Favoritender gesamten Komplexitätstheorie.

6 Andere Varianten von Kommunikationskomplexität

Wir schließen nun mit einigen besonders aktiven modernen Forschungsrich-tungen der Kommunikationskomplexitätstheorie.

Quantenkommunikation

Ich versuche lieber nicht, einen Quantencomputer zu definieren — vielleichthat der Leser bereits von diesem bis jetzt nicht konstruierten Gerät gehört.Es reicht zu wissen, dass man auch mit ihnen Kommunikationsprobleme lösenkann [28]. Sei Q(f) das entsprechende Komplexitätsmaß. Ein Quantencom-puter hat implizit Zugang zu zufälligen Bits, also Q(f) ≤ R(f). Anderer-seits gilt die Diskrepanzschranke (6) auch für Quantenprotokolle [16] undergibt für sie dieselbe Schranke wie in Theorem 7. Interessanter wird es,wenn wir die Disjunktheitsfunktion betrachten: Ihre Komplexität fällt vonn auf

√n [7, 25]. Die Frage, ob ein Quantenkommunikationsprotokoll mehr

als eine Quadratwurzel besser als das beste probabilistische Protokoll seinkann, gehört zu den wichtigsten und schwersten Problemen der Disziplin:

Offenes Problem 3. Kann man R(f) für Funktionen f : X × Y −→ {0, 1}durch ein Polynom in Q(f) abschätzen?

Mehrparteienkommunikation

Es gibt nun mehr als zwei Spieler Alice, Bob, Claire, Dylan, Eve. . . die ge-meinsam eine Funktion f auswerten wollen. Es ergeben sich wieder verschie-dene Modelle, je nachdem, wie man den Ausgangswert unter den Spielernverteilt. Im einfachsten Fall kennt jeder Spieler wieder nur seinen eigenenWert. Es stellt sich aber heraus, dass dieses Modell nicht so wichtig wiedas folgende Zahl-auf-der-Stirn-Modell ist (dieses hat enorm viele Anwen-dungen). In diesem wollen k Spieler weiterhin eine Funktion f(x1, . . . , xk),xi ∈ {0, 1}n auswerten. Der Haken ist dabei, dass jeder Spieler xi auf seiner


Stirn stehen hat, also alle Teile des Ausgangswert bis auf seinen eigenen sehenkann. Es sei Ck(f) die kleinste Anzahl von Bits, die die Spieler zur korrektenBerechnung von f(x1, . . . , xk) austauschen müssen; der Einfachheit halbernehmen wir an, dass jede Nachricht an alle anderen Spieler weitergeleitetwird.

Die Funktionen DISJn und IPn lassen sich in diesem Modell bis auf vomLeser leicht auszufüllende Details „eindeutig“ zu DISJkn und IPk

n fortsetzen.In der klassischen Arbeit [5] bewies man nun

Theorem 10. Ck(IPkn) ≥ Ω(n) für k ≤ ε log2 n, wobei ε > 0 eine hinrei-

chend kleine Konstante ist.

Könnte man nun dieses Ergebnis für irgendeine „gute“ Funktion f auf größereSpieleranzahlen fortsetzen, so würde man die Komplexitätstheorie revolutio-nieren, wie schon in [5] angedeutet wurde. Aber keine der uns bekanntenMethoden kann diesem Problem etwas anhaben.

Offenes Problem 4. Man zeige Ck(IPkn) ≥ nε für k = �(log2 n)2� und eine

beliebige aber feste Konstante ε > 0.

Selbst für k = 3 blieb die Kommunikationskomplexität von DISJkn langeZeit unbekannt. Erst vor kurzem wurde in [8, 18, 6] ein Durchbruch erzielt:Die Autoren zeigten für bis zu k = ε(log2 n)

1/3 Spieler nichttriviale untereSchranken für Ck(DISJkn).

Suchprobleme

Bis jetzt betrachteten wir nur Funktionen, die nur zwei Werte 0 und 1 anneh-men können. Solche Funktionen identifiziert man in der Komplexitätstheorienormalerweise mit Entscheidungsproblemen oder Sprachen. Nichts hindertuns aber daran, allgemeinere Funktionen f : X × Y −→ Z zu betrachten,wobei Z eine kompliziertere endliche Menge ist. Noch weiter gehend kannman sogar annehmen, dass die Funktion f mehrwertig ist. Dies bedeutet,dass es eine ternäre Relation R ⊆ X × Y × Z gibt, so dass es für jedes Paar(x, y) mindestens ein z ∈ Z (einen „Wert“ von f) mit (x, y, z) ∈ R gibt.Für gegebene (x, y) soll das Protokoll nun irgendein z ∈ Z mit (x, y, z) ∈ Rausgeben, an das wir sonst keine Bedingungen stellen. Aufgaben dieser Artheißen Suchprobleme.

Normalerweise ist die Komplexität von Suchproblemen noch schwerer zuanalysieren als die von Entscheidungsproblemen. Dies sieht man schon amfolgenden, von der Gleichheitsfunktion inspirierten Beispiel.

Es seien X,Y ⊆ {0, 1}n disjunkt: X ∩ Y = ∅. Dann ist EQ(x, y) = 0 füralle x ∈ X, y ∈ Y , und es gibt stets eine Position i, an der sich beide Werteunterscheiden: xi �= yi. Alice und Bob seien nun damit beauftragt, irgendeinesolche Position zu finden.

Dieses so unschuldig aussehende Kommunikationsproblem ist in Wahrheitäquivalent zum zweiten großen offenen Problem der Berechnungskomplexität


über die Tiefe von Berechnungen (der erste Platz wird von P vs. NP einge-nommen). Wir haben keine Ahnung, wie man hier untere Schranken zeigenkönnte. Ein einfacheres Problem können wir analog aus der Disjunktheits-funktion ableiten.

Wir nehmen also statt X ∩ Y = ∅ an, dass es für jeden Wert (x, y) ∈X × Y eine Position i mit xi = yi = 1 gibt. Alice und Bob sollen wieder einsolches i finden. Für dieses Problem konnte man in der Tat in [15, 22, 14]untere Schranken finden, die interessante Konsequenzen für die monotoneSchaltungstiefe Boolescher Funktionen tragen.

7 Zusammenfassung

Wir wollten in diesem Beitrag demonstrieren, wie schnell einfache, elementareund unschuldige Fragen zu jahrzehntelang offenen Problemen führen können.Neben den erwähnten gibt es noch viele weitere solche Herausforderungenin der Komplexitätstheorie, für die wir jungen und kreativen Nachwuchs be-nötigen. Wir hoffen daher, dass dieser Beitrag den Leser dazu verleitet, sichmehr mit diesem faszinierenden Thema zu beschäftigen.

Formelindex

Da wir in diesem Beitrag viele untypische Begriffe eingeführt haben, wollenwir hier die wichtigsten von ihnen zusammen mit einer kurzen Beschreibungund der ersten Seite, auf der sie auftauchen, auflisten.

Komplexitätsmaße

cost(P ) Kosten des Protokolls P — maximale Anzahl von Bits, die zur Be-rechnung der Funktion mittels P für irgendeinen Wert (x, y) über-tragen werden müssen 103

C(f) Kommunikationskomplexität (des schlimmsten Falls) der Funktionf — minimale Kosten eines f berechnenden Protokolls 103

χ(f) Partitionszahl einer Funktion f — kleinste Anzahl paarweisedisjunkter f -monochromatischer Rechtecke, die den Definitionsbe-reich von f überdecken 107

t(f) Überlagerungszahl der Funktion f — kleinste Anzahl f -monochromatischer Rechtecke, die den Definitionsbereich von füberdecken 109

χ0(f) kleinste Anzahl paarweise disjunkter f -monochromatischer Recht-ecke, die f−1({0}) überdecken 109


χ1(f) kleinste Anzahl paarweise disjunkter f -monochromatischer Recht-ecke, die f−1({1}) überdecken 109

t0(f) kleinste Anzahl f -monochromatischer Rechtecke, die f−1({0})überdecken 109

t1(f) Kleinste Anzahl f -monochromatischer Rechtecke, die f−1({1})überdecken (log2 t1(f) heißt nichtdeterministische Kommunikati-onskomplexität von f) 109

R(f) fehlerbeschränkte probabilistische Kommunikationskomplexität derFunktion f — minimale Kosten eines zufallsbasierten Protokolls,so dass das Ergebnis für jeden Wert mindestens mit Wahrschein-lichkeit 2

3 richtig ist 112U(f) fehlerunbeschränkte probabilistische Kommunikationskomplexität

der Funktion f — minimale Kosten eines zufallsbasierten Proto-kolls, so dass das Ergebnis für jeden Wert mit Wahrscheinlichkeitecht größer als 1

2 richtig ist 112Discu(f) Diskrepanz (unter Gleichverteilung) der Funktion f — größte

Differenz der Anzahlen der Urwerte von 0 und 1 in einem Rechteck(geteilt durch |X × Y |, wobei f auf X × Y definiert ist) 113

Q(f) Quantenkommunikationskomplexität der Funktion f — minimaleKosten eines f berechnenden Quantencomputerprotokolls 114

Ck(f) Mehrparteienkommunikationskomplexität der Funktion f — mi-nimale Anzahl von Bits, die k Spieler zur Berechnung von f aus-tauschen müssen (im Zahl-auf-der-Stirn-Modell) 115

Binäre Funktionen

EQN Gleichheitsfunktion — bildet {1, 2, . . . , N} × {1, 2, . . . , N} auf{0, 1} ab mit EQN (x, y) = 1 genau dann, wenn x = y ab 104

LEN Kleinergleich-Funktion — bildet {1, 2, . . . , N}×{1, 2, . . . , N} auf{0, 1} ab mit LEN (x, y) = 1 genau dann, wenn x ≤ y ab 108

DISJn Disjunktheitsfunktion („NAND“) — bildet {0, 1}n × {0, 1}n auf{0, 1} ab mit DISJn(x, y) = 1 genau dann, wenn xi = 0 oder yi = 0für alle i ≤ n ab 108

IPn Skalarprodukt mod 2 — bildet {0, 1}n × {0, 1}n auf {0, 1} abmit IPn(x, y) = 1 genau dann, wenn xi = yi = 1 für ungerade vielei ab 113

DISJkn verallgemeinerte Disjunktheitsfunktion — bildet ({0, 1}n)k auf{0, 1} ab mit DISJkn(x

1, . . . , xk) = 1 genau dann, wenn es für allei ≤ n ein ν ∈ {1, . . . , k} mit xν

i = 0 gibt, ab 115IPk

n verallgemeinertes Skalarprodukt mod 2 — bildet ({0, 1}n)k auf{0, 1} ab mit IPk

n(x1, . . . , xk) = 1 genau dann, wenn es ungerade

viele Indizes i mit x1i = x2

i = . . . = xki = 1 gibt 115


Funktionenwachstum6 und Diverses

O(f(n)) g(n) ≤ O(f(n)) genau dann, wenn es C > 0 mit g(n) ≤ Cf(n) füralle n gibt 104

Ω(f(n)) g(n) ≥ Ω(f(n)) genau dann, wenn es ε > 0 mit g(n) ≥ εf(n) füralle n gibt 108

�x� die kleinste ganze Zahl n ≥ x für x ∈ R 103

Literaturverzeichnis

[1] Alfred V. Aho, Jeffrey D. Ullman und Mihalis Yannakakis, On notions of informationtransfer in VLSI circuits. In: Proceedings of the 15th ACM Symposium on the Theoryof Computing, ACM Press, New York, 1983, 133–139.

[2] Noga Alon und Paul Seymour, A counterexample to the rank-coloring conjecture.Journal of Graph Theory 13 (1989), 523–525.

[3] Sanjeev Arora und Boaz Barak, Computational Complexity: A Modern Approach.Cambridge University Press, Cambridge, 2009.

[4] László Babai, Peter Frank und Janos Simon, Complexity classes in communicationcomplexity theory. In: Proceedings of the 27th IEEE Symposium on Foundations ofComputer Science, IEEE Computer Society, Los Alamitos, 1986, 337–347.

[5] László Babai, Noam Nisan und Márió Szegedy, Multiparty protocols, pseudorandomgenerators for logspace, and time-space trade-offs. Journal of Computer and SystemSciences 45 (1992), 204–232.

[6] Paul Beame und Dang-Trinh Huynh-Ngoc, Multiparty communication complexity andthreshold circuit size of AC0. Technical Report TR08-082, Electronic Colloquium onComputational Complexity, 2008.

[7] Harry Buhrman, Richard Cleve und Avi Wigderson, Quantum vs. classical communi-cation and computation. In: Proceedings of the 30th ACM Symposium on the Theoryof Computing, ACM Press, New York, 1998, 63–86; vorläufige Version verfügbar unterhttp://arxiv.org/abs/quant-ph/9802040 .

[8] Arkadev Chattopadhyay und Anil Ada, Multiparty communication complexity ofdisjointness. Technical Report TR08-002, Electronic Colloquium on ComputationalComplexity, 2008.

[9] Benny Chor und Oded Goldreich, Unbiased bits from sources of weak randomness andprobabilistic communication complexity. SIAM Journal on Computing 17 2 (1988),230–261.

[10] Jürgen Forster, A linear lower bound on the unbounded error probabilistic communi-cation complexity. Journal of Computer and System Sciences 65 4 (2002), 612–625.

[11] Martin Fürer, Faster integer multiplication. SIAM Journal on Computing 39 3 (2009),979–1005.

[12] Bala Kalyanasundaram und Georg Schnitger, The probabilistic communication com-plexity of set intersection. SIAM Journal on Discrete Mathematics 5 4 (1992), 545–557.

[13] Anatolii A. Karatsuba und Yuri P. Ofman, Multiplication of many-digital numbersby automatic computers. Proceedings of the USSR Academy of Sciences 145 (1962),293–294.

6 Traditionell auch g(n) = O(f(n)) und g(n) = Ω(f(n)); siehe auch Fußnote 3.


[14] Mauricio Karchmer, Ran Raz und Avi Wigderson, Super-logarithmic depth lowerbounds via direct sum in communication complexity. Computational Complexity 5(1995), 191–204.

[15] Mauricio Karchmer und Avi Wigderson, Monotone circuits for connectivity requiresuper-logarithmic depth. SIAM Journal on Discrete Mathematics 3 2 (1990), 255–265.

[16] Ilan Kremer, Quantum Communication. Masterarbeit, Hebräische Universität Jeru-salem, 1995.

[17] Eyal Kushilevitz und Noam Nisan, Communication Complexity. Cambridge Univer-sity Press, Cambridge, 1997.

[18] Troy Lee und Adi Shraibman, Disjointness is hard in the multiparty number-on-the-forehead model. Computational Complexity 18 2 (2009), 309–336.

[19] Kurt Mehlhorn und Erik M. Schmidt, Las Vegas is better than determinism in VL-SI and distributive computing. In: Proceedings of the 14th ACM Symposium on theTheory of Computing, ACM Press, New York, 1982, 330–337.

[20] Ramamohan Paturi und Janos Simon, Probabilistic communication complexity. Jour-nal of Computer and System Sciences 33 1 (1986), 106–123.

[21] Ran Raz und Boris Spieker, On the “log-rank”-conjecture in communication comple-xity. Combinatorica 15 4 (1995), 567–588.

[22] Alexander Razborov, Applications of matrix methods to the theory of lower boundsin computational complexity. Combinatorica 10 1 (1990), 81–93.

[23] Alexander Razborov, The gap between the chromatic number of a graph and the rankof its adjacency matrix is superlinear. Discrete Mathematics 108 (1992), 393–396.

[24] Alexander Razborov, On the distributional complexity of disjointness. TheoreticalComputer Science 106 (1992), 385–390.

[25] Alexander Razborov, Quantum communication complexity of symmetric predicates.Izvestiya: Mathematics 67 1 (2003), 145–159.

[26] Arnold Schönhage und Volker Strassen, Schnelle Multiplikation großer Zahlen. Com-puting 7 (1971), 281–292.

[27] Andrew Yao, Some complexity questions related to distributive computing. In: Pro-ceedings of the 11th ACM Symposium on the Theory of Computing, ACM Press, NewYork, 1979, 209–213.

[28] Andrew Yao, Quantum circuit complexity. In: Proceedings of the 34th IEEE Sympo-sium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos,1993, 352–361.

Documents

Eine Einladung in die Mathematik || Die Komplexität der Kommunikation