Kommunikationskomplexität… Klassen?

Diskussion :

Ich habe in letzter Zeit einige Zeit damit verbracht, verschiedene Dinge in der Komplexität der Kommunikation zu lernen. Zum Beispiel habe ich mich wieder mit dem relevanten Kapitel in Arora / Barak vertraut gemacht, angefangen, einige Artikel zu lesen, und das Buch von Kushilevitz / Nisan bestellt. Intuitiv möchte ich die Komplexität der Kommunikation mit der Komplexität der Berechnungen vergleichen. Und vor allem, ich bin beeindruckt von der Tatsache , dass die Berechnungskomplexität in eine reiche Theorie des Vergebens Rechenprobleme in Komplexitätsklassen entwickelt hat, von denen einige wiederum kann ( aus einer Perspektive, zumindest ) in Betracht gezogen im Hinblick auf den vollständigen Probleme für jede gegebene Klasse. Wenn Sie zum Beispiel jemandem zum ersten Mal erklären , ist es schwierig, Vergleiche mit SAT oder einem anderen NP-vollständigen Problem zu vermeiden.$NP$

Im Vergleich dazu habe ich noch nie etwas von einem analogen Konzept für Kommunikationskomplexitätsklassen gehört. Es gibt viele mir bekannte Beispiele für Probleme, die "für einen Satz vollständig" sind. Beispielsweise könnten die Autoren als allgemeinen Rahmen ein gegebenes Kommunikationsproblem und dann beweisen, dass ein verwandter Satz gilt, das Kommunikationsproblem in oder weniger Bits gelöst werden kann (für einige , die von dem spezifischen Satz / Problem abhängen) fragliches Paar). Die dann in der Literatur verwendete Terminologie ist, dass für "vollständig" ist .T i f f X X P $P$$T$$iff$$X$$X$$P$$T$

Darüber hinaus enthält der Entwurf des Kapitels zur Komplexität der Kommunikation zwischen Arora und Barak (der im endgültigen Druck entfernt / optimiert zu sein scheint) eine verlockende Zeile, in der es heißt: "Im Allgemeinen können Kommunikationsprotokolle analog zu , , usw. werden . " Ich bemerke jedoch zwei wichtige Auslassungen:c o N P P $NP$$coNP$$PH$

1. Das "analoge" Konzept scheint eine Methode zu sein, um die Kommunikationskomplexität beim Lösen eines bestimmten Protokolls mit Zugriff auf verschiedene Arten von Ressourcen zu berechnen, hört aber nur auf, geeignete Kommunikationskomplexitätsklassen zu definieren ...
2. Der größte Teil der Kommunikationskomplexität scheint in dem Sinne relativ "gering" zu sein, dass die überwiegende Mehrheit der Ergebnisse / Theoreme / etc. dreht sich um kleinräumige, spezifische polynomgroße Werte. Dies die Frage auf, warum beispielsweise für die Berechnung interessant ist, während das analoge Konzept für die Kommunikation weniger interessant zu sein scheint. (Natürlich könnte ich nur daran schuld sein, dass ich mich der Komplexitätskonzepte der Kommunikation auf "höherer Ebene" nicht bewusst bin.) $NEXP$

Frage (n) :

Gibt es ein analoges Konzept zu Rechenkomplexitätsklassen für die Kommunikationskomplexität?

Und:

Wenn ja, wie verhält es sich mit dem "Standard" -Begriff der Komplexitätsklassen? (zB gibt es natürliche Einschränkungen für "Kommunikationskomplexitätsklassen", die dazu führen, dass sie von Natur aus nicht die gesamte Bandbreite der rechnerischen Komplexitätsklassen abdecken?) Wenn nicht, warum sind Klassen ein interessanter Formalismus für rechnerische Komplexität, aber nicht für die Komplexität der Kommunikation?

Anscheinend suchen Sie nach diesem Artikel: http://portal.acm.org/citation.cfm?id=1382439.1382962

Komplexitätsklassen in Kommunikationskomplexität wurden von Babai, Frankl, Simon in dem von Noam zitierten Aufsatz vorgestellt. Das Papier entwickelt auch die Idee der Vollständigkeit unter geeigneten Reduzierungen. Wenn Sie zum Beispiel die Klassen NP und co-NP beschreiben, ist es sehr sinnvoll, auch das Disjointness-Problem (co-NP complete) zu beschreiben.

Was Ihre zweite Frage betrifft, wenn P (in Kommunikationskomplexität) die mit Polylog (n) -Kommunikation deterministisch lösbare Problemklasse ist, dann sollte die Klasse EXP die mit Poly (n) -Kommunikation lösbare Problemmenge sein, was einfach alles ist. Es scheint also, dass solche Klassen nicht interessant sind.

Es gibt jedoch eine andere Möglichkeit, größere Klassen zu erhalten. Bereits PSPACE wird (von Babai et al.) Nicht als Raumbegriff, sondern als Wechselbegriff definiert. Interaktive Beweise sind ein weiterer Weg, um große Komplexitätsklassen zu erhalten. Sie können also die Klasse MIP als den Satz von Problemen definieren, die in einem Kommunikationsspiel mit zwei Prüfern (die nicht miteinander sprechen können) und zwei Prüfern (die miteinander und mit den Prüfern sprechen können) gelöst werden können.

In der Turing-Maschinenwelt ist MIP = NEXP, aber wie steht es mit der Komplexität der Kommunikation (wo NEXP keinen Sinn zu ergeben scheint)? Erstens ist MIP nicht nur die Menge aller Probleme, die sich aus einem einfachen Zählargument ergeben.

Andrew Drucker (in seiner Masterarbeit) hat etwas Interessantes an dieser Klasse gezeigt. Er betrachtet die Komplexität von PCPs in Bezug auf die Kommunikation, die (nach Standardtechniken) MIP-Protokollen entsprechen (sein Ergebnis ist etwas stärker als hier angegeben).

Was er zeigt, ist, dass für jedes Problem in NP (der Turing-Maschinenklasse) und für jede Art der Aufteilung der Eingaben das resultierende Kommunikationsproblem ein MIP-Protokoll mit Kommunikations-Polylog (n) aufweist (dh das Problem liegt in der (Kommunikationskomplexität). Klasse MIP).

Obwohl MIP nicht alles ist, sollte es schwierig sein, ein explizites Problem zu finden, das sich nicht in MIP befindet (nicht, weil wir keine Probleme finden können, die sich nicht in NP befinden, sondern weil es nicht einfach ist, sich vorzustellen, wie die Komplexität der Turing-Maschine ins Spiel kommen kann ).

Dass es schwierig ist, Untergrenzen für MIP aufzuzeigen, dürfte nicht allzu überraschend sein, da wir nicht einmal wissen, wie man Untergrenzen für AM-Protokolle beweist.

Ein Abschnitt des Complexity Zoos listet die wichtigsten Kommunikationskomplexitätsklassen auf.

Der grundlegende Grund für diese Einschränkungen der Kommunikationskomplexität besteht darin, dass immer nur eine lineare Menge an Gesamtinformationen (die Eingaben) kommuniziert werden muss. Obwohl Hartmut Klauck in seiner Antwort bereits im Wesentlichen darauf hingewiesen hat, wollte ich eine Antwort auf das andere OQ in Bezug auf den Grund für diese grundlegende Einschränkung hervorheben, nämlich, dass die Spieler rechnerisch unbegrenzt sind .

$d(n)$$O(d(n)\log n)$$d(n)=O(1)$