Złożoność informacji algorytmów zapytań?

Złożoność informacji jest bardzo przydatnym narzędziem w złożoności komunikacji, stosowanym głównie w celu ograniczenia złożoności komunikacyjnej rozproszonych problemów.

Czy istnieje analogia złożoności informacji dla złożoności zapytań? Istnieje wiele podobieństw między złożonością zapytań a złożonością komunikacji; często (ale nie zawsze!) dolna granica w jednym modelu zostaje przetłumaczona na dolną granicę w drugim modelu. Czasami to tłumaczenie jest dość nietrywialne.

Czy istnieje pojęcie złożoności informacji, która jest przydatna w przypadku niższych granic złożoności problemów związanych z zapytaniami?

Pierwsze przejście wydaje się wskazywać, że złożoność informacji nie jest zbyt użyteczna; na przykład złożoność zapytania przy obliczaniu OR z bitów wynosi Ω ( N ) dla algorytmów losowych i Ω ( $N$$\Omega(N)$przypadku algorytmów kwantowych, podczas gdy najprostsza adaptacja pojęcia złożoności informacji wskazuje, że informacja wyuczona przez dowolny algorytm kwerendy ma co najwyżejO(logN)(ponieważ algorytm zatrzymuje się, gdy zobaczy pierwszą1na wejściu).$\Omega(\sqrt{N})$$O(\log N)$$1$

Tak, teoria informacji jest przydatna do udowodnienia niższych granic złożoności zapytań problemów w informatyce.

Alexander Golynski podał dobry przykład w swojej przełomowej pracy zatytułowanej „Dolne granice sondy komórkowej dla zwięzłych struktur danych”, zaprezentowanej na SODA 2009. Wykorzystuje teorię informacji do udowodnienia dolnej granicy złożoności zapytań, co z kolei daje niższą granicę w model sondy bitowej dla (zwięzłych) struktur danych. Możesz pobrać artykuł z pamięci podręcznej Cititeera lub z repozytorium ACM . Wydaje się, że nie ma wersji czasopisma tego artykułu.

Być może zainteresują Cię także następujące artykuły z jego bibliografii, które również wiążą złożoność komunikacji z teorią informacji:

• Peter Bro Miltersen, Noam Nisan, Shmuel Safra i Avi Wigderson. O strukturach danych i asymetrycznej złożoności komunikacji. Journal of Computer and System Sciences, 57 (1): 37–49, 1998. [link]
• Anna Gal i Peter Bro Miltersen. Złożoność sond komórkowych w zwięzłych strukturach danych. W International Colloquium na temat automatów, języków i programowania, strony 332–344, 2003. [link]