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

22

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

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

Jeśli chodzi o drugą nierówność, łatwo jest podać (nieskończoną rodzinę) relacji z log 2 ( p p ( R ) ) = c c ( R ) .Rlog2(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=3c=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 .Rcc(R)/(2o(1))log2(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 ?cclog2L

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.
Hermann Gruber
źródło
Nie wiedziałem o drugim odnośniku i próbowałem google go znaleźć i nie znalazłem wersji online. Czy masz link?
Marcos Villagra
czy to jest strona główna autora? mpi-inf.mpg.de/~doerr
Marcos Villagra
Tak, to jest strona główna autora. Link do citeseerX, którego użyłem do pobrania papieru, wydaje się zniknąć. Możesz zapytać w bibliotece, czy mogą otrzymać wydruk; ale najlepiej zapytać autora, czy jest gotów umieścić go na swojej stronie głównej, czy na arxivie.
Hermann Gruber
2
Jedyną ostatnią rzeczą, która może być przydatna, o której wiem, jest ten papier lab2.kuis.kyoto-u.ac.jp/~kenya/MFCS2010.pdf .
Hartmut Klauck
2
Naprawdę nie rozumiem, za co oferujecie nagrodę. Chcesz mniejszą stałą zamiast 3?
Sam

Odpowiedzi:

10

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.

domotorp
źródło
1
2L+A+B1L+R+A+B+C=1C0LR
3

c2c1.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.

Hermann Gruber
źródło
1
Ten rozdział dotyczy Formuł, a nie złożoności komunikacji, ale dowody rzeczywiście wyglądają podobnie. Czy te problemy są równoważne?
domotorp
Tak, te problemy są równoważne. Dowodem są gry Karchmer-Wigderson. Patrz np. Twierdzenie 3.13 w książce Jukny. (Zwróć uwagę, że równoważność obowiązuje dla formuł DeMorgan, a nie dla ogólnych form boolowskich w pełnym zakresie.)
Hermann Gruber,
W grach KW celem jest znalezienie innej współrzędnej, jeśli obietnica jest taka, że ​​f (x) różni się od f (y), więc ogólnie różni się od złożoności komunikacji.
domotorp