Numer podziału protokołu i deterministyczna złożoność komunikacji

Oprócz (deterministycznej) złożoności komunikacji $cc(R)$ relacji $R$ , inną podstawową miarą ilości potrzebnej komunikacji jest numer podziału protokołu $pp(R)$ . Zależność między tymi dwoma miarami jest znana aż do stałego współczynnika. Monografia Kushilevitza i Nisana (1997) daje

Jeśli chodzi o drugą nierówność, łatwo jest podać (nieskończoną rodzinę) relacji z log 2 ( p p ( R ) ) = c c ( R ) .$R$$\log_2(pp(R)) = cc(R)$

Jeśli chodzi o pierwszą nierówność, Doerr (1999) wykazał, że możemy zastąpić współczynnik w pierwszej granicy c = 2,223 . O ile w ogóle można poprawić pierwszą granicę? $c=3$$c=2.223$

Dodatkowa motywacja wynikająca ze złożoności opisowej: poprawa stałej spowoduje poprawę dolnej granicy minimalnego rozmiaru wyrażeń regularnych odpowiadających danemu DFA opisującemu pewien skończony język, patrz Gruber i Johannsen (2008). $2.223$

Chociaż nie jest to bezpośrednio związane z tym pytaniem, Kushilevitz, Linial i Ostrovsky (1999) podali relacje z c c ( R ) / ( 2 - o ( 1 ) ) ≥ log 2 ( r p ( R ) ) , gdzie r p ( R ) to numer partycji prostokąta .$R$$cc(R)/(2-o(1)) \ge \log_2(rp(R))$$rp(R)$

EDYCJA: Zauważ, że powyższe pytanie jest równoważne z następującym pytaniem w złożoności obwodu logicznego: Jaka jest optymalna stała tak że każda boolowska formuła DeMorgan wielkości liścia L może zostać przekształcona w równoważną formułę głębokości co najwyżej c log 2 L ?$c$$c \log_2L$

Referencje :

• Kushilevitz, Eyal; Nisan, Noam: Złożoność komunikacji. Cambridge University Press, 1997.
• Kushilevitz, Eyal; Linial, Nathan; Ostrovsky, Rafail: Hipoteza o liniowej macierzy w złożoności komunikacyjnej jest fałszywa, Combinatorica 19 (2): 241–254, 1999.
• Doerr, Benjamin: Złożoność komunikacji i numer partycji protokołu, sprawozdanie techniczne 99-28, Berichtsreihe des Mathematischen Seminars der Universität Kiel, 1999.
• Gruber, Hermann; Johannsen, Jan: Optymalne dolne granice rozmiaru wyrażeń regularnych przy użyciu złożoności komunikacji. W: Foundation of Software Science and Computation Structures 2008 (FoSSaCS 2008), LNCS 4962, 273-286. Skoczek.

Ok, więc spróbuję udowodnić, że dwa wystarczą, to znaczy . Przykro mi, ale czasami piszę liście zamiast liczby liści / pp (R), ilekroć liczba jest mniejsza niż 1, oczywiście mam na myśli to. Ponadto zwykle piszę <zamiast ≤, aby poprawić czytelność nietekstową.$cc(R)\le 2\log_2(pp(R))$$\le$

Pośrednio załóżmy, że istnieje R, dla którego nie jest to prawdą, i weźmy R z najmniejszą możliwą pp (R), która narusza nierówność. Zasadniczo musimy pokazać, że używając dwóch bitów, możemy zmniejszyć o połowę liczbę liści we wszystkich czterech wynikach drzewa protokołu, a następnie skończymy przy użyciu indukcji.

Oznacz możliwy zestaw danych wejściowych Alice przez X i Boba przez Y. Weź środek drzewa protokołu, które osiąga liście pp (R), tj. Usuwając węzeł, który drzewo dzieli na trzy części, z których każda ma najwyżej 1/2 liści pp (R) i oznaczają odpowiednie dane wejściowe przez X0 i Y0. Bez utraty ogólności możemy przypuszczać, że Alicja mówi w środku, a ona mówi, czy jej dane wejściowe należą do XL czy XR, których rozłącznym związkiem jest X0. Oznacz stosunek liści do pp (R) w XL Y0 przez L, w XR$\times$ Y0 przez R, a resztę przez D. Teraz dzielimy resztę na trzy kolejne części, podobnie jak Doerr, oznaczając liście, których prostokąt przecinają Y0 × X przez A, którego prostokąt przecina X0 × Y przez B, a pozostałe przez C. Zauważ, że A + B + C = D.$\times$$\times$$\times$

Teraz wiemy, że L + R> 1/2, L, R <1/2 i bez utraty ogólności możemy założyć, że L wynosi co najwyżej R. Wiemy również D = A + B + C <1/2. Wynika z tego, że 2L + A + B <1, z którego wiemy, że albo L + A <1/2 lub L + B <1/2, będą to nasze dwa przypadki.

Przypadek L + A <1/2: Najpierw Bob mówi, czy jego dane wejściowe należą do Y0, czy nie. Jeśli nie, pozostało co najwyżej D <1/2 liści. Jeśli tak, to Alicja mówi, czy jej dane wejściowe należą do XR, czy nie. Jeśli nie, pozostało co najwyżej L + A <1/2 liści. Jeśli tak, to pozostało nam R <1/2 liści.

Przypadek L + B <1/2: Pierwsza Alice mówi, czy jej dane wejściowe należą do XR, czy nie. Jeśli tak, to Bob mówi, czy jego należy do Y0, czy nie, w zależności od tego pozostały nam R lub B. Jeśli dane wejściowe Alicji nie są w XR, to Alicja mówi, czy dane wejściowe są w XL, czy nie. Jeśli tak, to pozostało L + B <1/2 liści. Jeśli nie, pozostało co najwyżej D <1/2 liści.

We wszystkich przypadkach jesteśmy skończeni. Powiedz mi co myślisz.

$c\le 2$$c \le 1.73$

Referencje

Stasys Jukna. Złożoność funkcji logicznej: postępy i granice. Springer, 2012.

VM Chrapczenko. O związku między złożonością a głębią. Metody Diskretnogo Analiza in Synthezis of Control Systems 32: 76–94, 1978.