Existe uma generalização da teoria da informação em informações polinomialmente conhecíveis?

Peço desculpas, essa é uma pergunta "suave".

A teoria da informação não tem conceito de complexidade computacional. Por exemplo, uma instância do SAT ou uma instância do SAT mais um pouco indicando satisfação carregam a mesma quantidade de informações.

Existe uma maneira de formalizar o conceito de "polinomialmente conhecível"?

Tal estrutura poderia definir, por exemplo, a noção de divergência polinomial-KL entre uma variável aleatória X relativa a Y como o número de bits necessários para calcular X no tempo polinomial dado Y.

Da mesma forma, a entropia de uma variável aleatória X pode ser definida como o número de bits necessários para codificar X de uma maneira que possa ser decodificada em tempo polinomial.

Essa generalização foi estudada? Pode ser feito consistente?

$U$$t(n)$$x$$y$$U$$K^t_U(x | y)$$U$$p$$U$$U(p,y)=x$$U(p,y)$$t(|x|)$

No entanto, nesse cenário limitado pelo tempo, nem todos os teoremas usuais da teoria da informação são conhecidos por manter. Por exemplo, sabe-se que a simetria da informação é válida para a complexidade usual de Kolmogorov (sem limite de tempo), mas não é conhecida como válida para o tempo. Veja, por exemplo, o capítulo 6 da tese de Troy Lee .

Se você está preocupado que isso se aplique a cadeias de caracteres, e não a distribuições, sugiro a leitura dos seguintes documentos, que dizem que, de fato, a complexidade das cadeias de Kolmogorov e a entropia de distribuições de Shannon estão intimamente relacionadas:

• Grunwald e Vitanyi. Informação de Shannon e complexidade de Kolmogorov

• Martelo, Romashchenko, Shen, Vereshchagin. Desigualdades para a entropia de Shannon e a complexidade de Kolmogorov .

(Por outro lado, há algumas propriedades conhecidas por não serem compartilhadas entre as duas; consulte Muchnik & Vereshchagin, Shannon Entropy vs. Kolmogorov Complexity .)

Uma questão é que muitos dos teoremas a que estamos acostumados na teoria da informação não se sustentam no mundo computacional. Portanto, mesmo se formalizássemos um análogo computacional da entropia, a teoria resultante pode não se parecer mais com a teoria da informação.

$f$$H(f(X)) \le H(X)$$H(f(X)) \le H(X)$

Não estou ciente de um modelo computacional teroético da informação, mas há aplicações claras da teoria da informação na complexidade computacional.

$n \log n$

Mais tipicamente, os resultados da teoria da informação podem servir como limites mais baixos para a complexidade computacional. Por exemplo, o resultado "teórico da informação" de Yao na complexidade da comunicação {1} implica limites inferiores computacionais para determinar se dois conjuntos são iguais. Aplicações mais sofisticadas de complexidade de comunicação fornecem compensações de espaço-tempo para máquinas de Turing {2}.

{1} Yao, Andrew Chi-Chih. "Algumas questões de complexidade relacionadas à computação distributiva (relatório preliminar)." Anais do décimo primeiro simpósio anual da ACM sobre Teoria da Computação. ACM, 1979.

Eyal Kushilevitz: complexidade da comunicação. Advances in Computers 44: 331-360 (1997).