Protokollpartitionsnummer und deterministische Kommunikationskomplexität

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) gibt$cc(R)$$R$ $pp(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 .$R$$\log_2(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=3$$c=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 .$R$$cc(R)/(2-o(1)) \ge \log_2(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 ?$c$$c \log_2L$

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.

$cc(R)\le 2\log_2(pp(R))$$\le$

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.

$\times$$\times$$\times$$\times$

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.

$c\le 2$$c \le 1.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.