Protokollpartitionsnummer und deterministische Kommunikationskomplexität

22

Neben der (deterministischen) Kommunikationskomplexität einer Beziehung R ist die Protokollpartitionsnummer p p ( R ) ein weiteres grundlegendes Maß für den Kommunikationsbedarf . Die Beziehung zwischen diesen beiden Maßen ist bis zu einem konstanten Faktor bekannt. Die Monographie von Kushilevitz und Nisan (1997) gibtcc(R)R pp(R)

cc(R)/3log2(pp(R))cc(R).

In Bezug auf die zweite Ungleichung ist es einfach, (eine unendliche Familie von) Beziehungen mit log 2 ( p p ( R ) ) = c c ( R ) anzugeben .Rlog2(pp(R))=cc(R)

In Bezug auf die erste Ungleichung zeigte Doerr (1999), dass wir den Faktor in der ersten Schranke durch c = 2,223 ersetzen können . Um wie viel kann die erste Grenze, wenn überhaupt, verbessert werden? c=3c=2.223

Zusätzliche Motivation aus der Komplexität der Beschreibung: Die Verbesserung der Konstante führt zu einer verbesserten Untergrenze für die Mindestgröße regulärer Ausdrücke, die einem gegebenen DFA entspricht und eine endliche Sprache beschreibt, siehe Gruber und Johannsen (2008). 2.223

Obwohl nicht direkt mit dieser Frage verwandt, gaben Kushilevitz, Linial und Ostrovsky (1999) Beziehungen mit c c ( R ) / ( 2 - o ( 1 ) ) log 2 ( r p ( R ) ) an , wobei r p ( R ) ist die Nummer der Rechteckpartition .Rcc(R)/(2o(1))log2(rp(R))rp(R)

BEARBEITEN: Beachten Sie, dass die obige Frage der folgenden Frage in der Booleschen Schaltungskomplexität entspricht: Was ist die optimale Konstante so dass jede boolesche DeMorgan-Formel von Blattgröße L in eine äquivalente Tiefenformel von höchstens c log 2 L transformiert werden kann ?cclog2L

Referenzen :

  • Kushilevitz, Eyal; Nisan, Noam: Kommunikationskomplexität. Cambridge University Press, 1997.
  • Kushilevitz, Eyal; Linial, Nathan; Ostrovsky, Rafail: Die Linear-Array-Vermutung in der Kommunikationskomplexität ist falsch, Combinatorica 19 (2): 241-254, 1999.
  • Doerr, Benjamin: Kommunikationskomplexität und die Protokollteilungsnummer, Technischer Bericht 99-28, Berichtsreihe des Mathematischen Seminars der Universität Kiel, 1999.
  • Gruber, Hermann; Johannsen, Jan: Optimale untere Schranken für die Größe regulärer Ausdrücke mit Hilfe der Kommunikationskomplexität. In: Grundlagen von Software Science und Computation Structures 2008 (FoSSaCS 2008), LNCS 4962, 273-286. Springer.
Hermann Gruber
quelle
Ich wusste nichts über die zweite Referenz, habe versucht, sie zu googeln, und keine Online-Version gefunden. Hast du einen Link?
Marcos Villagra
Ist dies die Homepage des Autors? mpi-inf.mpg.de/~doerr
Marcos Villagra
Ja, dies ist die Homepage des Autors. Der citeseerX-Link, den ich zum Herunterladen des Papiers verwendet habe, scheint weg zu sein. Sie können in Ihrer Bibliothek nachfragen, ob sie eine Hardcopy erhalten können. Am besten ist es jedoch, den Autor zu fragen, ob er bereit ist, es auf seine Homepage oder auf arxiv zu stellen.
Hermann Gruber
2
Das einzige, was mir in letzter Zeit nützlich sein könnte, ist dieses Papier lab2.kuis.kyoto-u.ac.jp/~kenya/MFCS2010.pdf .
Hartmut Klauck
2
Ich verstehe wirklich nicht, wofür du das Kopfgeld anbietest. Sie möchten eine kleinere Konstante anstelle von 3? Sie zitieren das Doerr-Papier selbst, wo es auf 2.223 verbessert wurde ...
domotorp

Antworten:

10

cc(R)2log2(pp(R))

Nehmen wir indirekt an, dass es ein R gibt, für das dies nicht zutrifft, und nehmen wir das R mit dem kleinstmöglichen pp (R), das die Ungleichung verletzt. Wir müssen im Grunde zeigen, dass wir mit zwei Bits die Anzahl der Blätter in allen vier Ergebnissen des Protokollbaums halbieren können, dann sind wir mit der Induktion fertig.

××××

Jetzt wissen wir, dass L + R> 1/2, L, R <1/2 und ohne Verlust der Allgemeinheit können wir annehmen, dass L höchstens R ist. Wir kennen auch D = A + B + C <1/2. Daraus folgt, dass 2L + A + B <1, woraus wir wissen, dass entweder L + A <1/2 oder L + B <1/2, dies unsere beiden Fälle sind.

Fall L + A <1/2: Zuerst sagt Bob, ob seine Eingabe zu Y0 gehört oder nicht. Wenn nicht, haben wir höchstens noch D <1/2 Blätter übrig. Wenn ja, sagt Alice, ob ihre Eingabe zu XR gehört oder nicht. Wenn nicht, haben wir höchstens noch L + A <1/2 Blätter übrig. Wenn ja, dann haben wir R <1/2 Blätter übrig.

Fall L + B <1/2: Zuerst sagt Alice, ob ihre Eingabe zu XR gehört oder nicht. Wenn ja, sagt Bob, ob er zu Y0 gehört oder nicht, je nachdem, ob R oder B übrig sind. Wenn die Eingabe von Alice nicht in XR ist, sagt Alice, ob ihre Eingabe in XL ist oder nicht. Wenn ja, dann haben wir noch L + B <1/2 Blätter. Wenn nicht, haben wir höchstens noch D <1/2 Blätter.

In allen Fällen sind wir fertig. Lass mich wissen was du denkst.

domotorp
quelle
1
2L+A+B1L+R+A+B+C=1C0LR
3

c2c1.73

Verweise

Stasys Jukna. Boolesche Funktionskomplexität: Fortschritte und Grenzen. Springer, 2012.

VM Khrapchenko. Auf eine Beziehung zwischen der Komplexität und der Tiefe. Metody Diskretnogo Analiza in Synthezis of Control Systems 32: 76–94, 1978.

Hermann Gruber
quelle
1
In diesem Kapitel geht es um Formeln und nicht um Kommunikationskomplexität, aber die Beweise sehen in der Tat ähnlich aus. Sind diese Probleme gleichbedeutend?
Domotorp
Ja, diese Probleme sind gleichbedeutend. Der Beweis erfolgt über Karchmer-Wigderson-Spiele. Siehe z. B. Satz 3.13 in Juknas Buch. (Beachten Sie, dass die Äquivalenz für DeMorgan-Formeln gilt, nicht für allgemeine boolesche Formeln auf der gesamten Basis.)
Hermann Gruber,
In KW-Spielen besteht das Ziel darin, eine andere Koordinate zu finden, wenn das Versprechen lautet, dass sich f (x) von f (y) unterscheidet, und sich daher von der Kommunikationskomplexität im Allgemeinen deutlich unterscheidet.
Domotorp