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

15

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.Ω(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).Ω(N.)O(logN.)1

Henry Yuen
źródło

Odpowiedzi:

5

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]
Jeremy
źródło