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

9

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?

Arthur B
fonte
11
Você já tentou fazer isso no Cryptography SE crypto.stackexchange.com ?
Zsbán Ambrus
2
É possível que o pessoal de criptografia tenha uma resposta, mas a pergunta está perfeitamente relacionada ao assunto aqui, e eu suspeito que possa ter uma chance melhor de obter uma boa resposta aqui. Apenas uma observação rápida: não poste novamente a mesma pergunta no Crypto.SE; a postagem cruzada em vários sites SE é proibida pelas regras do site.
DW

Respostas:

9

Ut(n)xyUKUt(x|y)UpUU(p,y)=xU(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:

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

Joshua Grochow
fonte
Minha principal preocupação seria que o tempo depende da máquina de Turing. Como as máquinas de Turing podem emular-se mutuamente com uma aceleração ou desaceleração polinomial, penalizar a complexidade por log (log (t)) parece torná-las equivalentes a uma constante aditiva. No entanto, a complexidade de Levin usa log (t), não sei por que.
Arthur B
11
t(n)loglogt
2

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.

fH(f(X))H(X)H(f(X))H(X)

DW
fonte
Eu entendo, eu apenas me pergunto o quanto pode ser recuperado ou corrigido. Nesse caso, você pode adicionar a restrição de que f é polinomialmente invertida, mas que se sente ad-hoc
Arthur B
Sinto que a semente contém mais informações do que a sequência psuedo-aleatória gerada, pois podemos calcular a sequência gerada a partir da semente.
precisa
@ Kaveh, se você estiver falando em um sentido teórico da informação: se o gerador pseudoaleatório for invertível (talvez não em tempo polinomial, mas em princípio), então sua entrada e saída terão a mesma quantidade de informação, teoricamente; caso contrário, se o subjetivo pseudo-aleatório for invertível, você estará certo.
DW
0

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.

nlogn

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

Ari Trachtenberg
fonte