Mehrparteien-Kommunikationskomplexität von „Partitionsproblem festlegen“

13

In einer Anwendung, die ich in Betracht ziehe, muss ich die Kommunikationskomplexität des folgenden Problems kennen:

Bei sei S die Menge von ganzen Zahlen von 1 bis n . Alice, Bob und Carol erhalten jeweils eine Teilmenge von S , die mit A , B bzw. C bezeichnet ist. Sie wollen prüfen , ob A , B und C eine Teilung bilden S , das heißt, sie sind disjunkt und ihre Vereinigung ist S .nS1nSABCABCSS

Ich interessiere mich besonders für den Fall von 3 Parteien, aber andere Fälle wären auch interessant. Beachten Sie, dass für den Fall von 2 Parteien das Problem dem GLEICHHEITSPROBLEM äquivalent ist, sodass es für deterministische Protokolle eine untere Schranke von , für randomisierte Protokolle eine obere Schranke von O ( log n ) aufweist .Ω(n)O(logn)

Meine Frage ist, ob dieses Problem vorher bekannt ist. Wenn Sie irgendwelche Probleme kennen, die damit zusammenhängen könnten, würde mich das ebenfalls interessieren.

Danu
quelle

Antworten:

17

Eine lineare Untergrenze für deterministisches CC folgt, indem eine der Mengen als leer festgelegt wird.

Für eine obere Schranke, erste Note randomisierten logarithmisch , dass dieses Problem auf das Problem reduziert werden kann , ob die Summe von drei fragen 3n - Bit - Zahlen ist genau 23n1 . Diese kann in O(logn) randomisierter Kommunikation gelöst werden, indem die Spieler mod einer zufälligen O(logn) -Bit-Primzahl bedienen.

Noam
quelle
Können Sie nicht stattdessen Bit-Zahlen verwenden und einen Algorithmus erhalten, der auch in einem Streaming-Modell funktioniert? Damit dies funktioniert, müssen Sie auch überprüfen, ob die Gesamtzahl der Elemente korrekt ist. Dies ist jedoch einfach. Carries zerstören einen, also ist die Summe von n Zweierpotenzen genau dann 2 n - 1, wenn es genau eine Kopie jeder Zweierpotenz gibt. 2nn2n1
Warren Schudy
1

Ich untersuche eine etwas andere Frage, die verwandt zu sein scheint. Was wäre eine gute Referenz für Details zur randomisierten Obergrenze in der obigen Antwort?

Keren
quelle
1
Vielleicht solltest du eine andere Frage stellen?
Suresh Venkat
Als Antwort auf mein Problem können Sie das zufällige Protokoll zur Lösung des Gleichstellungsproblems heranziehen, um eine Vorstellung davon zu bekommen. Zum Beispiel Beispiel 3.5 in Nissan-Kushilevitzs Buch. Die Hauptidee ist, Fingerabdrücke zu verwenden, denke ich.
Danu