Complexidade das informações dos algoritmos de consulta?

A complexidade da informação tem sido uma ferramenta muito útil na complexidade da comunicação, usada principalmente para limitar a complexidade da comunicação de problemas distribuídos.

Existe um análogo da complexidade da informação para a complexidade da consulta? Existem muitos paralelos entre a complexidade da consulta e a complexidade da comunicação; muitas vezes (mas nem sempre!) um limite inferior em um modelo é convertido em um limite inferior no outro modelo. Às vezes, essa tradução é bastante trivial.

Existe uma noção de complexidade da informação que seja útil para limitar a complexidade da consulta dos problemas?

Uma primeira passagem parece indicar que a complexidade da informação não é muito útil; por exemplo, a complexidade da consulta para calcular OR de bits é Ω ( N ) para algoritmos aleatórios e Ω ( $N$$\Omega(N)$para algoritmos quânticos, enquanto a adaptação mais direta da noção de complexidade da informação indica que as informações aprendidas por qualquer algoritmo de consulta são no máximoO(logN)(porque o algoritmo para quando vê o primeiro1na entrada).$\Omega(\sqrt{N})$$O(\log N)$$1$

Sim, a teoria da informação é útil para provar limites mais baixos na complexidade de consultas de problemas em Ciência da Computação.

Alexander Golynski deu um bom exemplo em seu artigo inovador intitulado "Limites inferiores da sonda celular para estruturas de dados sucintas", apresentado na SODA 2009. Ele usa a teoria da informação para provar um limite mais baixo na complexidade da consulta, que por sua vez gera um limite mais baixo no modelo de sonda de bits para estruturas de dados (sucintas). Você pode fazer o download do documento no cache do cidadão ou no repositório do ACM . Parece não haver uma versão em periódico do artigo.

Você pode também estar interessado nos seguintes artigos de sua bibliografia, que também relacionam a complexidade da comunicação com a teoria da informação:

• Peter Bro Miltersen, Noam Nisan, Shmuel Safra e Avi Wigderson. Sobre estruturas de dados e complexidade de comunicação assimétrica. Journal of Computer and System Sciences, 57 (1): 37–49, 1998. [link]
• Anna Gal e Peter Bro Miltersen. A complexidade da sonda celular de estruturas de dados sucintas. No Colóquio Internacional sobre Autômatos, Idiomas e Programação, páginas 332–344, 2003. [link]