Numéro de partition du protocole et complexité déterministe de la communication

Outre la complexité de communication (déterministe) d'une relation , une autre mesure de base pour la quantité de communication nécessaire est le numéro de partition de protocole . La relation entre ces deux mesures est connue jusqu'à un facteur constant. La monographie de Kushilevitz et Nisan (1997) donne$cc(R)$$R$ $pp(R)$

Concernant la seconde inégalité, il est facile de donner (une famille infinie de) relations avec .log 2 ( p p ( R ) ) = c c ( R $R$$\log_2(pp(R)) = cc(R)$

Concernant la première inégalité, Doerr (1999) a montré que l'on peut remplacer le facteur dans la première borne par . Dans quelle mesure la première borne peut-elle être améliorée, le cas échéant? c = $c=3$$c=2.223$

Motivation supplémentaire de la complexité de la description: l'amélioration de la constante se traduira par une borne inférieure améliorée sur la taille minimale des expressions régulières équivalente à un DFA donné décrivant un langage fini, voir Gruber et Johannsen (2008). $2.223$

Bien que n'étant pas directement lié à cette question, Kushilevitz, Linial et Ostrovsky (1999) ont donné les relations avec , où est le numéro de partition rectangulaire .c c ( R ) / ( 2 - o ( 1 ) ) ≥ log 2 ( r p ( R ) ) r p ( R $R$$cc(R)/(2-o(1)) \ge \log_2(rp(R))$$rp(R)$

EDIT: notez que la question ci-dessus est équivalente à la question suivante dans la complexité du circuit booléen: quelle est la constante optimale $c$ telle que chaque formule booléenne DeMorgan de leafsize L puisse être transformée en une formule équivalente de profondeur au plus $c \log_2L$ ?

Références :

• Kushilevitz, Eyal; Nisan, Noam: Complexité de la communication. Cambridge University Press, 1997.
• Kushilevitz, Eyal; Linial, Nathan; Ostrovsky, Rafail: The Linear-Array Conjecture in Communication Complexity is False, Combinatorica 19 (2): 241-254, 1999.
• Doerr, Benjamin: Communication Complexity and the Protocol Partition Number, Technical Report 99-28, Berichtsreihe des Mathematischen Seminars der Universität Kiel, 1999.
• Gruber, Hermann; Johannsen, janvier: limites inférieures optimales sur la taille des expressions régulières en utilisant la complexité de la communication. Dans: Foundations of Software Science and Computation Structures 2008 (FoSSaCS 2008), LNCS 4962, 273-286. Springer.

Ok, alors laissez-moi essayer de prouver que deux suffisent, c'est-à-dire . Désolé mais parfois j'écris des feuilles au lieu du nombre de feuilles / pp (R), chaque fois que le nombre est inférieur à 1, je le pense évidemment. De plus, j'écris généralement <au lieu de pour améliorer la lisibilité non tex.$cc(R)\le 2\log_2(pp(R))$$\le$

Supposons indirectement qu'il existe un R pour lequel ce n'est pas vrai et prenons le R avec le plus petit pp (R) possible qui viole l'inégalité. Nous devons essentiellement montrer qu'en utilisant deux bits, nous pouvons diviser par deux le nombre de feuilles dans les quatre résultats de l'arbre de protocole, puis nous avons terminé par induction.

Notons l'ensemble possible d'entrées d'Alice par X et de Bob par Y. Prenez le centre de l'arbre de protocole qui obtient les feuilles pp (R), c'est-à-dire le nœud supprimant lequel l'arbre tombe en trois parties, chacune ayant au plus 1/2 des feuilles pp (R) et désignent les entrées correspondantes par X0 et Y0. Sans perte de généralité, nous pouvons supposer qu'Alice parle au centre et qu'elle dit si son entrée appartient à XL ou XR, dont l'union disjointe est X0. Notons le rapport des feuilles à pp (R) en XL Y0 par L, en XR Y0 par R et dans le reste par D. Maintenant, nous divisons le reste en trois autres parties, de la même manière que Doerr, désignant les feuilles dont le rectangle coupe Y0 X par A, dont le rectangle coupe X0$\times$$\times$$\times$$\times$ Y par B et le reste par C. Notez que A + B + C = D.

Nous savons maintenant que L + R> 1/2, L, R <1/2 et sans perte de généralité, nous pouvons supposer que L est au plus R. Nous connaissons également D = A + B + C <1/2. Il s'ensuit que 2L + A + B <1, dont nous savons que soit L + A <1/2 ou L + B <1/2, ce seront nos deux cas.

Cas L + A <1/2: le premier Bob indique si son entrée appartient à Y0 ou non. Sinon, il nous reste au plus D <1/2 feuilles. Si c'est le cas, Alice indique si son entrée appartient à XR ou non. Sinon, il nous reste au plus L + A <1/2 feuilles. Si c'est le cas, il nous reste R <1/2 feuilles.

Cas L + B <1/2: d'abord Alice indique si son entrée appartient à XR ou non. Si c'est le cas, alors Bob indique si son appartenance à Y0 ou non, selon cela, il nous reste R ou B feuilles. Si l'entrée d'Alice n'est pas en XR, Alice indique si son entrée est en XL ou non. Si c'est le cas, il nous reste L + B <1/2 feuilles. Sinon, il nous reste au plus D <1/2 feuilles.

Dans tous les cas, nous avons terminé. Laissez-moi savoir ce que vous pensez.

En plus de l'excellente réponse de domotorp donnant le , permettez-moi de mentionner que la récente monographie de Jukna (2012) fournit une discussion approfondie de cette question au chapitre 6.1. Selon Jukna, la meilleure limite actuelle est par Khrapchenko (1978).$c\le 2$$c \le 1.73$

Les références

Stasys Jukna. Complexité de la fonction booléenne: avancées et frontières. Springer, 2012.

VM Khrapchenko. Sur une relation entre la complexité et la profondeur. Metody Diskretnogo Analiza dans Synthezis of Control Systems 32: 76–94, 1978.