Kommunikationskomplexität mit einem Schiedsrichter

Nehmen Sie einen Rahmen für die Kommunikationskomplexität an, in dem wir zwei Spieler A (Läuse) und B (ob) und einen R (eferee) haben. A und B kommunizieren nicht direkt miteinander. In jeder Kommunikationsrunde sendet jeder von ihnen eine Nachricht ( , ) an das R. R berechnet zwei Funktionen und und sendet die Ergebnisse an sie. Die Funktionen sind festgelegt. Die Idee ist, dass die Kommunikation zwischen den Spielern eingeschränkt ist. Darüber hinaus kann der Schiedsrichter die Nachrichten bearbeiten. $m_A$ $m_B$ $f_A(m_A,m_B)$ $f_B(m_A,m_B)$

Beispiel:

A und B senden zwei (beliebig große) Zahlen an R, R prüft, welche davon größer ist und informiert die Spieler.

In diesem Rahmen können wir ein einfaches Protokoll entwerfen, das die folgende Funktion mit einer einzigen Runde einfach berechnet. A und B senden und an R, R gibt die Antwort an sie zurück und sie geben die Antwort aus. $x$ $y$

f (x, y) = {\begin{cases} 0 & x \leq y \\ 1 & o w \end{cases}

$f(x,y)= \begin{cases}0 & x\leq y\\ 1 & ow \end{cases}$

Offensichtlich ist dies kein interessanter Fall, da die von uns berechnete Funktion mit den Schiedsrichterfunktionen identisch ist. Ein interessanterer Fall ist, wenn wir eine feste lineare Ungleichung haben und die Werte für die Variablen zwischen den Spielern aufgeteilt sind (A. hat und B hat ). Die Aufgabe besteht darin, zu entscheiden, ob die Ungleichung korrekt ist. Das Protokoll in diesem Fall ist, dass die Spieler ihren Teil berechnen und sie dann an den Schiedsrichter senden. $\vec{a} \cdot \vec{x} \leq \vec{b} \cdot \vec{y}$ $\vec{x}$ $\vec{y}$

Frage:

Wurde diese Art von Kommunikationskomplexität untersucht? Wenn ja, wo kann ich mehr darüber erfahren?

Anmerkung 1: Auf Seite 49 erwähnen Kushilevitz und Nisan einen Rahmen, an dem ein Schiedsrichter beteiligt ist, der sich jedoch sehr von dem zu unterscheiden scheint, was ich verlange.

Anmerkung 2: Ich bin nicht sicher, ob es richtig ist, R als Schiedsrichter zu bezeichnen. Bitte kommentieren Sie, wenn Sie einen besseren Vorschlag haben.

cc.complexity-theory reference-request communication-complexity Kaveh
quelle

Das Modell, das Sie erwähnen, heißt "Simultaneous Message Passing"

Marcos Villagra

Überprüfen Sie dieses Dokument ( arxiv.org/abs/quant-ph/0102001 ) und seine Referenzen. Überprüfen Sie insbesondere die Papiere von Ambainis sowie Newman und Szegedy.

Marcos Villagra

Hier ist ein neueres Papier von Raoul Jahin ieeexplore.ieee.org/xpl/…

Marcos Villagra

@MarcosVillagra: SMP ist dasselbe wie Kavehs Note 1, nicht wahr?

Alessandro Cosentino

@Marcos, danke, ich werde sie überprüfen, aber basierend auf den Abstracts scheint es mir, dass SMP sich von dem unterscheidet, was ich beschreibe. (Ich werde versuchen, ein besseres Beispiel zu finden, um zu verdeutlichen, dass die Spieler R verwenden, um zu kommunizieren, was mehrere Runden dauern kann.) Ps: Ich denke, es wäre besser, wenn Sie diese Kommentare als Antwort posten.

Kaveh

Antworten:

Ich bin mir sicher, dass Sie das folgende Papier kennen, aber ich habe einen Link dazu eingefügt, weil andere Leser interessiert sein könnten: Interpolation nach Spielen

Dieses Papier ist ein Versuch, das Kommunikationskomplexitäts-Framework zu verwenden, um untere Grenzen für das Schneiden von Ebenen aufzuzeigen. Das Protokoll wird verwendet, um eine Interpolationsschaltung für einen nicht erfüllbaren CNF zu erzeugen:

A (x, y) \lor B (x, z) .

$A(x,y)\lor B(x,z).$

Spieler erhält Eingabe und , Spieler erhält und . Wenn es in Schnittebenen einen flachen baumartigen Beweis gibt, haben die beiden Spieler ein solches Kommunikationsprotokoll $A$ $a$ $y^a$ $B$ $b$ $z^b$

Jede Kommunikation wird vom Schiedsrichter vermittelt, was bei der Bewertung der Ungleichheiten im Beweis hilft.
Der Kommunikationsaufwand ist gering (der Baum ist flach).
Die beiden Spieler entscheiden entweder, welcher von oder gefälscht ist. $A$ $B$
sie finden eine Position in der . $i$ $a_i \not= b_i$

Der Schiedsrichter wird in ein Wahrscheinlichkeitsprotokoll für Ungleichheiten umgewandelt. Auf diese Weise ist es möglich, die Untergrenze für baumartige probabilistische Protokolle im Rahmen der Kommunikationskomplexität in eine Untergrenze für baumartige Proofs für Schnittebenen umzuwandeln.

Wenn wir eine Untergrenze für das Kommunikationsprotokoll in Form eines PLS hätten, würden wir eine Untergrenze für dag-ähnliche Schnittebenen-Proofs erhalten.

Beachten Sie, dass diese Technik nicht von den tatsächlichen Inferenzregeln zum Schneiden von Ebenen abhängt. Wenn wir annehmen, dass die Inferenzregeln (1) positive Kombination (2) ganzzahlige Division mit Floor sind, können wir die monotone Interpolationsschaltung unter Verwendung des Pavel Pudlák- Arguments erstellen .

MassimoLauria
quelle

Eigentlich habe ich versucht herauszufinden, ob etwas Allgemeineres als dies in Bezug auf die Kommunikationskomplexität untersucht wurde, daher habe ich die unteren Grenzen der Beweiskomplexität und die mögliche Interpolation nicht erwähnt, um die Antworten nicht zu verzerren, aber danke. :)

Kaveh

Ja, das habe ich mir gedacht. Aber andere Leser dieses Forums könnten interessiert sein und sich dafür interessieren, die Komplexität zu beweisen.

MassimoLauria

Nur ein paar Bemerkungen. Erstens kann ich nicht genau verstehen, warum wir überhaupt einen Schiedsrichter brauchen. Wenn seine / ihre Funktion für die Spieler bekannt ist, warum können sie dann nicht einfach den Schiedsrichter simulieren? Alice sendet an Bob, er (ohne ) berechnet , danach berechnet er und teilt Alice das Ergebnis mit. Vielleicht gehen davon aus , dass ist nicht zu Bob bekannt ist , und zu Alice? $m_A$ $m_A$ $m_B$ $f(m_A,m_B)$ $f_A$ $f_B$

Zweitens sind Protokolle, die sich auf lineare Ungleichungen beziehen, in der Tat im Zusammenhang mit Proofs zum Schneiden von Ebenen interessant. In diesem Fall reicht es sogar aus, Protokolle zu berücksichtigen, bei denen die Form von Nachrichten sehr eingeschränkt ist : Es können nur Werte einiger linearer Kombinationen von Eingabevariablen übertragen werden.

Um etwas genauer zu sein, nehmen wir an, wir erhalten ein System linearer Ungleichungen mit ganzzahligen Koeffizienten. Wir wissen, dass das System keine - Lösung hat. Die Variablen sind irgendwie unter den Spielern aufgeteilt (auf fünfzig-fünfzig-Weise); Dies ist das Szenario der "schlechtesten Partition": Der Gegner kann die "schlechteste" Partition auswählen. Bei einer - Saite ist es das Ziel der Spieler, eine unbefriedigte Ungleichung zu finden. Das heißt, die Antwort ist jetzt kein einzelnes Bit, sondern der Name einer Ungleichung unseres Systems. (Dies ist ein Kommunikationsspiel vom Typ Karchmer-Wigderson.) $0$ $1$ $0$ $1$

Betrachten Sie nun die folgenden eingeschränkten Protokolle für ein solches Spiel: (i) Die Schiedsrichter funktionieren, wenn nur wenn ist. (Ii) Die Nachrichten der Spieler sind auf lineare beschränkt : In jeder Runde Alice die Nachricht von der Form muss senden und Bob die Nachricht von der Form . $f(\alpha,\beta)=1$ $\alpha \leq \beta$ $m_A(\vec{x})=\vec{c}\cdot \vec{x}$ $m_B(\vec{y})=\vec{d}\cdot \vec{y}$

Impagliazzo, Pitassi und Urquhart (1994) beobachteten Folgendes: Wenn alle in den Schnittebenenbeweisen verwendeten Koeffizienten in der Anzahl der Variablen polynomisch sind und dieses Spiel Kommunikationsbits benötigt, dann jeder baumartige Beweis für die Unbefriedigung der Das gegebene System muss Ungleichungen erzeugen . Sie verwendeten dann bekannte Untergrenzen für die Kommunikationskomplexität, um ein explizites System zu erhalten, das Beweise für eine exponentielle Größe erfordert. Der Nachteil dieses Ergebnisses ist, dass das System sehr künstlich ist , es entspricht keinem "echten" Optimierungsproblem. Es ist daher eine interessante Frage, eine Untergrenze für "echte" Optimierungsprobleme zu finden. $t$ $\exp(t/\log n)$

$G=(V,E)$ $u$ $x_u$ $\sum_{v\in V}x_v>\alpha(G)$ $x_u+x_v\leq 1$ $uv$ $G$ $0$ $1$ $G$

$=(L\cup R,E)$ $A\subseteq L$ $B\subseteq R$ $|A\cup B|>\alpha(G)$ $A$ $B$ $\alpha(G)$ $L$ $R$ $n\times n$ $\omega(\log^2 n)$

@Kaveh: Entschuldigen Sie, dass Sie Ihre Frage mit Fragen "beantwortet" haben.

Stasys
quelle

Ich interessiere mich mehr für das allgemeine CC-Framework als für seine bekannten Anwendungen in Bezug auf die Komplexität von Beweisen. Die vom Schiedsrichter verwendeten Funktionen sind bekannt (sie sind wie gesagt festgelegt). Es gibt eine Reihe von Fragen, warum ich an diesem Modell interessiert bin, aber der Hauptpunkt ist, wie wir den Umfang der Kommunikation messen werden. Wenn wir an der Gesamtzahl der übertragenen Bits interessiert sind, können Sie das Protokoll wie gesagt simulieren. Aber wenn wir einige andere Komplexitätsmaße wie die Anzahl der Runden berücksichtigen wollen, dann denke ich, dass es anders ist. Zum Beispiel in einem Fall, der in

Kaveh

Beweiskomplexität Jeder Spieler sendet eine reelle Zahl an den Schiedsrichter. Eine reelle Zahl kann unendlich viele Bits codieren. Wenn Sie dies simulieren möchten, müssen wir unendlich viele Bits senden. Wenn wir dies zulassen, können wir einfach die gesamte Eingabe senden, sodass dies uninteressant wird. Wenn wir jedoch die Anzahl der Runden im Rahmen mit einem Schiedsrichter zählen, erhalten wir ein anderes Maß, das nützlich sein kann (wie in Pavel Pudlaks Beweis).

Kaveh

O (\log n)

$O(\log n)$

n

$n$

Dies sind Nebenprobleme, da ich, wie gesagt, mehr über die Art der Kommunikationskomplexität erfahren möchte, die ich in der Frage beschrieben habe, und absichtlich vermieden habe, sie mit Beweiskomplexität und Interpolationen zu verknüpfen. Die Aussage meiner Frage hat nichts mit Beweiskomplexität zu tun.

Kaveh

k > 2

$k>2$