Aplicações de complexidade Kolmogorov em complexidade computacional

Informalmente, a complexidade de Kolmogorov de uma string é o comprimento de um programa mais curto que gera . Podemos definir uma noção de 'string aleatória' usando-a ( é aleatório se ) É fácil ver que a maioria das strings é aleatória (não há tantos programas curtos).$x$$x$$x$$K(x) \geq 0.99 |x|$

A teoria da complexidade de Kolmogorov e a teoria da informação algorítmica são bastante desenvolvidas atualmente. E há vários exemplos divertidos de usar a complexidade de Kolmogorov em provas de diferentes teoremas que não contêm nada sobre a complexidade de Kolmogorov em suas declarações ( LLL construtiva , desigualdade de Loomis-Whitney e assim por diante).

Existem boas aplicações da complexidade de Kolmogorov e da teoria algorítmica da informação na complexidade computacional e campos relacionados ? Eu sinto que deve haver resultados que usem a complexidade de Kolmogorov como uma substituição direta de argumentos simples de contagem. Obviamente, isso não é tão interessante.

Lance Fortnow escreveu um artigo sobre este tópico: Complexidade de Kolmogorov e Complexidade Computacional

Você também deve conferir Uma introdução à complexidade de Kolmogorov e suas aplicações, de Li e Vitanyi, o livro definitivo sobre o assunto. Em particular, o capítulo 6 "O Método da Incompressibilidade" discute várias aplicações complexas, como uma prova de complexidade de Kolmogorov do lema de comutação de Hastad (do Circuit Lower Bounds à Kolmogorov de Fortnow e Laplante).

E existem aplicações na complexidade da comunicação (por exemplo, Complexidade de Kolmogorov e Métodos Combinatórios na Complexidade da Comunicação por Kaplan e Laplante).

Apenas alguns dias atrás, Scott Aaronson usou um argumento baseado na complexidade de Kolmogorov para mostrar a Equivalência de Amostragem e Pesquisa . Além disso, ele argumenta que, em seu argumento, a complexidade de Kolmogorov é usada de maneira essencial, que não é apenas um atalho para um argumento de contagem.

Este resultado de Alon et al. pode ser obtido por meio da complexidade de Kolmogorov.

"O conjunto de arestas E de todo gráfico bipartido finito pode ser dividido em subconjuntos para que todos os gráficos bipartidos resultantes sejam quase regulares".$\mathrm{poly}(\log |E|)$

Um excelente artigo que eu conheço (além dos outros excelentes artigos mencionados em outras respostas):

Juris Hartmanis, Complexidade generalizada de Kolmogorov e a estrutura das computações viáveis , FOCS 1983.

A principal coisa que me lembro desse artigo é uma construção baseada na complexidade de Kolmogorov de um oráculo que separa P de NP.

Outro artigo que vem à mente é

Allender et al., Power from Random Strings , FOCS 2002 ( versão ECCC ) e SICOMP 2006 .

Se bem me lembro, o último artigo separa a completude de Turing em tempo polinomial da completude de muitos espaços no log do PSPACE, usando argumentos de complexidade de Kolmogorov. Obviamente, ele faz muitas outras coisas, mas eu lembro que a separação é uma aplicação que é de interesse independente fora da teoria da informação algorítmica.

Há também uma técnica quântica de limite inferior que usa a complexidade de Kolmogorov:

" Limites inferiores para complexidade de consultas aleatórias e quânticas usando argumentos de Kolmogorov ", de Sophie Laplante e Frederic Magniez

(Primeiro, uma piada.) Quando confrontado com um problema difícil na complexidade computacional, sempre há a alegria da complexidade aplicada de Kolmogorov em elevar o espírito. Isso também é conhecido como código de golfe . Para uma variedade de pequenos problemas correspondentes às strings , pode-se explorar a complexidade intrínseca competitivamente em http://codegolf.com/ ou apenas por diversão em http://golf.shinh.org/ (com 80 diferentes idiomas no último site para o qual as constantes do Teorema da Invariância precisam ser estimadas). Como em todas as funções indecidíveis, aproxime-se com cautela.K ( s $s$$K(s)$

(Agora, para a parte mais séria.) Daniil Musatov mostrou recentemente que a des randomização ingênua pode fornecer construções razoáveis ​​para objetos que geralmente demonstram existir de maneira não construtiva através do método probabilístico. Eu acho que isso provavelmente fornecerá aplicações futuras significativas da complexidade de Kolmogorov, limitada por recursos, à complexidade computacional.

• Daniil Musatov, Aprimorando a versão limitada do espaço do teorema da complexidade condicional de Muchnik por meio da derandomização `` ingênua '' , CSR 2011, LNCS 6651, 64–76. doi: 10.1007 / 978-3-642-20712-9_6 ( pré-impressão )

Veja também artigos que citam este .

(Editar: link para a versão posterior publicada).

H. Buhrman, L. Fortnow e S. Laplante. A complexidade de Kolmogorov, limitada por recursos, revisitada. SIAM Journal on Computing, 31 (3): 887-905, 2002. ( jornal , página de Lance na web ).

Inclui aplicativos de complexidade Kolmogorov, como:

• Uma prova de Valiant-Vazirani
• Atribuições satisfatórias de fórmulas booleanas podem ser enumeradas no polinômio de tempo no tamanho da saída se uma atribuição exclusiva puder ser encontrada rapidamente
• Uma nova prova de que o BPP está no Sigma_2 P
• Várias construções oracle

Alguns dos itens acima foram comprovados pela primeira vez neste artigo, enquanto outros são simplesmente novas provas de velhos teoremas, usando a complexidade de Kolmogorov.

Aplicações da complexidade limitada de Kolmogorov na teoria da complexidade são uma boa pesquisa de Eric Allender sobre outras aplicações. Embora muitos dos resultados aqui sejam implicações, alguns são aplicativos verdadeiros, como os seguintes:

• Cor 13: Em relação a um oráculo genérico, não há gerador pseudo-aleatório seguro contra adversários de P / poli.
• Thm 16 [Allender e Gore, 1991]: Existe um oráculo em relação ao qual todos os predicados de NE são solucionáveis ​​em tempo exponencial e E = Union_k \ Sigma_k-TIME (n).

Ambas as provas usam a complexidade de Kolmogorov significativamente.

Um exemplo é o seguinte resultado descrito na pesquisa de Bogdanov e Trevisan : existe uma distribuição modo que a linguagem é fácil em média em relação a se for a pior das hipóteses.$D$$D$

Descrição mínima O comprimento usa a complexidade de Kolmogorov (ou aproximações e generalizações, devido à indecidibilidade) na aprendizagem teórica da informação e na teoria da inferência. Especificamente, o MDL é usado para encontrar explicações de dados que evitam naturalmente o super ajuste.

Jorma Rissanen fornece uma boa introdução ao seu conceito: http://www.mdl-research.org/jorma.rissanen/pub/Intro.pdf

Você quer dizer algo assim, ilyaraz?

http://arxiv.org/abs/1004.3993