Oprócz (deterministycznej) złożoności komunikacji relacji , inną podstawową miarą ilości potrzebnej komunikacji jest numer podziału protokołu . 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 ) .
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ę?
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).
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 .
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 ?
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.
źródło
Odpowiedzi:
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)≤2log2(pp(R)) ≤
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× 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.× × ×
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.
źródło
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.
źródło