Kommunikationskomplexität beim Finden eines gemeinsamen Elements zweier Teilmengen

Angenommen, Alice empfängt eine Teilmenge und Bob empfängt . Es wird versprochen, dass . Was ist die zufällige Kommunikationskomplexität bei der Bestimmung des gemeinsamen Elements ? $S \subseteq \{1,\dots,n\}$ $T \subseteq \{1,\dots,n\}$ $\lvert S \cap T \rvert = 1$ $S \cap T$

Mein Interesse daran ist wie folgt. Die Null-Kommunikationskosten für dieses Problem sind da Alice und Bob mit öffentlichen Münzen erraten und abbrechen können, wenn sie falsch raten. Ich kann mir jedoch kein -Kosten-Kommunikationsprotokoll vorstellen. Da nicht bekannt ist, ob die Kommunikationskosten Null viel geringer sind als die zufälligen Kommunikationskosten, denke ich, dass mir hier etwas Offensichtliches fehlt. $\log n$ $S \cap T$ $O(\log n)$

Die Kommunikationskosten Null sind wie folgt definiert. Nachdem Alice und Bob ihre Eingaben erhalten haben, dürfen sie überhaupt nicht mehr kommunizieren. Sie teilen sich jedoch öffentliche Münzen und dürfen mit "Abbruch" antworten. Wenn keine der beiden Parteien Abbrüchen, müssen sie die richtige Antwort mit bieten Wahrscheinlichkeit. Die Kommunikationskosten Null sind das negative Protokoll der Wahrscheinlichkeit, nicht abzubrechen. In arxiv: 1204.1505 wird (unter anderem) gezeigt, dass fast alle bekannten Untergrenzen der Kommunikationskomplexität tatsächlich Untergrenzen für die Nullkommunikation sind. $2/3$

Update: @Shitikanth hat gezeigt, dass die Kommunikationskomplexität beträgt . Anscheinend ergibt dies eine Lücke zwischen Kommunikationskosten und Null-Kommunikationskosten. Aber arxiv: 1204.1505 scheint den Eindruck zu erwecken, dass keine solche Lücke bekannt ist. Was vermisse ich? $\Omega(n)$

communication-complexity Dan Stahlke
quelle

"Alice und Bob können

mit öffentlichen Münzen erraten und abbrechen, wenn sie falsch raten." Ich glaube nicht, dass ihre Definition von Zero-Communication-Protokollen es Alice und Bob ermöglicht, nach dem Erraten abzubrechen. Wenn beide antworten, müssen sie mit hoher Wahrscheinlichkeit gewinnen.

S \cap T

$S\cap T$

Shitikanth

Entschuldigung für die schlampige Sprache. Zur Verdeutlichung wählen sie

mit öffentlichen Münzen. Alice wird abgebrochen , wenn

und Bob Abbrüchen wenn

. Wenn keine Partei abbricht, antworten sie

. Diese Art von Spielerei wird manchmal als "Raten" bezeichnet.

i \in {1, \dots, n}

$i \in \{1,\dots,n\}$

i \notin S

$i \not\in S$

i \notin T

$i \not\in T$

i

$i$

Dan Stahlke

Ich verstehe, was du jetzt meinst. Dies ist jedoch nur ein mögliches Null-Kommunikationsprotokoll für dieses Problem. Die Autoren beschreiben ein anderes Protokoll, das mit einer Wahrscheinlichkeit von nur

abbrechen würde .

2^{- O (n)}

$2^{-O(n)}$

Shitikanth

arxiv: 1204.1505 zeigt, dass die Kosten eines möglichen Nullkommunikationsprotokolls (ZC) mit einheitlicher Abbruchwahrscheinlichkeit (über die Eingaben) durch nahezu alle bekannten Techniken zur Senkung der Kommunikationskosten niedriger begrenzt sind. Das Protokoll ich schon erwähnt , hat Kosten

\log n

$\log n$

Dan Stahlke

Antworten:

(Reduzierung der eingestellten Disjunktheit)

$S, T \subseteq [n]$ $|S\cap T| \leq 1$ $S$ $T$ $X$ $X$ $S$ $T$ $O(\log n)$

$S$ $T$ $\Omega(n)$

Shitikanth
quelle

Ja natürlich danke! Ich wusste, dass die Antwort Disjunktheit beinhalten sollte, aber ich konnte es nicht sehen. Bevor ich die Frage abschließe, würde ich gerne sehen, ob sich jemand zu der offensichtlichen Lücke zwischen Kommunikation und Kommunikationskosten von Null äußert.

Dan Stahlke

Ich bin mir nicht sicher, was Sie unter Kommunikationskosten verstehen. Können Sie einen Link oder eine Referenz angeben?

Shitikanth

Ich habe die Frage mit einem Link zu einem Papier aktualisiert und werde auch die Definition für die ZC-Kosten bereitstellen.

Dan Stahlke

S \cap T

$S \cap T$

| S \cap T | = 1

$\lvert S \cap T \rvert = 1$

| S \cap T | > 1

$\lvert S \cap T \rvert > 1$

Ω (n)

$\Omega(n)$

E Q (s_{1}, t_{1}) \lor E Q (s_{2}, t_{2}) \lor \dots \lor E Q (s_{n}, t_{n}) .

$EQ(s_1,t_1)\lor EQ(s_2,t_2)\lor \dots \lor EQ(s_n,t_n).$

x_{1} y_{1} \lor x_{2} y_{2} \lor \dots \lor x_{n} y_{n} .

$x_1y_1\lor x_2y_2\lor\dots\lor x_ny_n.$ Die Kommunikationskomplexität dieser beiden Probleme ist äquivalent, da Gleichheit zu konstanten randomisierten Kommunikationskosten erfolgen kann.

$i$ $s_i=t_i$ $IP$ $IP$ $IP$ $\Theta(n)$

Ich hoffe das hilft.

Philippe Lamontagne
quelle

-3

Das schnellste Protokoll, das ich mir vorstellen kann, ist das alternative Austauschen eines zufälligen benachbarten Elementpaares, wobei Dinge weggeworfen werden, die übersprungen werden.

Alice [1,10,26,49,50] Bob [2,3,25,49,51]

Alice benachbartes Paar ist [10,26], also wirft Bob 25 weg

Alice [1,49,50] Bob [2,3,49,51]

Bob benachbartes Paar ist [3,49] Match auf 49 also halt

Chad Brewbaker
quelle