Complexidade de Kolmogorov

Em ciência da computação teórica e matemática , mais precisamente na teoria da informação , a complexidade de Kolmogorov , ou complexidade aleatória , ou complexidade algorítmica de um objeto - número, imagem digital , string - é o tamanho do menor algoritmo (em uma certa linguagem de programação fixa) que gera este objeto. Recebeu o nome do matemático Andrei Kolmogorov , que publicou sobre o assunto em 1963. Às vezes também é chamado de complexidade de Kolmogorov-Solomonoff . Essa quantidade pode ser vista como uma avaliação de uma forma de complexidade do objeto.

Exemplos

Primeiro exemplo - strings de texto

Considere dois textos, cada um composto por uma sequência de 32 caracteres:

abababababababababababababababab e 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7

O primeiro desses dois textos pode ser gerado pelo abalgoritmo " 16 vezes", ou seja, por um algoritmo de 10 caracteres, enquanto o segundo não parece ter nenhum pequeno algoritmo que o gere além do algoritmo que consiste em escrever este cadeia de caracteres, ou seja, um algoritmo de 32 caracteres. Assim, o primeiro texto parece ter uma complexidade de Kolmogorov menor que a do segundo.

Segundo exemplo - uma imagem

A figura à direita mostra uma imagem bitmap que mostra o conjunto de Mandelbrot . Esta imagem de 24 bits pesa 1,61 mebabytes. Por outro lado, um pequeno algoritmo pode reproduzir esta imagem a partir da definição matemática do conjunto de Mandelbrot e das coordenadas dos cantos da imagem. Portanto, a complexidade de Kolmogorov da imagem de bitmap (descompactada) é menor que 1,61 mebibytes em um modelo computacional razoável.

Definição

Considere uma máquina de computador $M$ capaz de executar programas. Esta máquina é considerada universal quando pode emular qualquer outra máquina de computador. A máquina de Turing universal é um exemplo.

Denotamos $P M$ todos os programas escritos para a máquina $M$ . Para um programa $p \in P M$ , denotamos por $l ( p )$ seu comprimento em número de instruções para a máquina $M$ e $s ( p )$ sua saída. A complexidade de Kolmogorov $K M ( x )$ , ou complexidade algorítmica, de uma sequência finita $x$ de caracteres para uma máquina $M$ é definida por:

K_M (x) = \ min_ {p \ em P_M} \ {l (p), s (p) = x \}

É, portanto, o comprimento do menor programa escrito para a máquina $M$ que gera a seqüência $x$ . Uma sequência constante tem baixa complexidade porque os programas que a geram podem ser muito curtos.

Resta ver até que ponto a função $K M ( x )$ depende da máquina $M$ , pois é bem possível imaginar uma máquina com instruções simples para gerar certas sequências complexas. A resposta é a seguinte: existe uma máquina universal $U$ (muitas vezes chamada aditivamente ótima) tal que para qualquer máquina $M$ existe uma constante $c M$ verificando para qualquer sequência $x$ a desigualdade:

K_U (x) \ leq K_M (x) + c_M

Intuitivamente, $c M$ é o comprimento de uma concha (ou emulador ), escrito para a máquina de $L$ , a linguagem utilizada pela máquina $M$ . Falamos então da universalidade da complexidade de Kolmogorov, no sentido de que ela não depende, exceto por uma constante aditiva, da máquina considerada.

Uma sequência pode então ser considerada tanto mais “aleatória” quanto maior sua complexidade em comparação com seu tamanho. Deste ponto de vista, os decimais dos números $π$ , $e$ ou √ 2 não são realmente aleatórios, pois existem algoritmos muito simples para calculá-los.

Uma dificuldade adicional reside no fato de que a complexidade de Kolmogorov não é decidível : podemos dar um algoritmo que produza o objeto desejado, o que prova que a complexidade desse objeto é no máximo do tamanho desse algoritmo. Mas você não pode escrever um programa que forneça a complexidade de Kolmogorov de qualquer objeto que você queira fornecer como entrada.

O conceito, tratado com cuidado, no entanto acaba por ser a fonte de muitos resultados teóricos.

Por exemplo, chama-se número incompressível no sentido de Kolmogorov um real cujo desenvolvimento p-ádico (binário para mais conveniência) é comparável ao tamanho do algoritmo que torna possível calculá-lo. Nesse sentido, todos os racionais e alguns irracionais são compressíveis, em particular números transcendentes como $π$ , $e$ ou 0,12345678910111213 ... cuja expansão binária é infinita, mas a sequência de decimais é perfeitamente computável. Por outro lado, o chamado número de Chaitin $Ω$ não é: esse número mede a probabilidade de uma máquina, fornecida por um programa composto de bits aleatórios, parar. A topologia dos números incompressíveis é interessante: intuitivamente concebemos que este conjunto é denso em , mas é impossível exibir algoritmicamente um real incompressível, pois isso equivaleria a dar-lhe um método de cálculo eficiente. Além disso, podemos mostrar que todos os números incompressíveis são normais , a sequência de seus decimais deve ser aleatória no sentido forte. $\ mathbb {R}$

Propriedades

A complexidade de Kolmogorov não é calculável . Em outras palavras, não existe um programa de computador que tome s como entrada e retorne K ( s ). Para provar isso, vamos raciocinar pelo absurdo e supor que tal função de Kolmo exista. Denotamos por k o tamanho desta função (ou seja, o número de caracteres de seu código-fonte). Poderíamos então escrever o seguinte algoritmo:

n := 1 Tant que Kolmo(n) < k + 100 faire: n := n + 1 Fin du Tant que écrire n

Assim, esse algoritmo escreve o menor número para ter uma complexidade de Kolmogorov maior que k + 100 (esse número necessariamente existe porque há apenas um número finito de programas de tamanho menor que k + 100 e há uma infinidade de números naturais).

Mas o algoritmo acima é escrito precisamente com menos de k + 100 caracteres: ele é, portanto, de complexidade menor que k + 100, e ele escreve precisamente um número de complexidade maior que k + 100, o que é absurdo (podemos aproximar esta observação ao argumento usado para o paradoxo de Berry ).

Portanto, não há função que calcule a complexidade de Kolmogorov.

Variantes com recursos limitados

A definição da complexidade de Kolmogorov é definida em termos do menor programa que produz x. Mas este programa pode consumir recursos significativos. Por isso, é importante levar em consideração os recursos utilizados pelo programa. Seja U uma máquina universal. Aqui está uma versão limitada pelo tempo t:

${\ displaystyle C ^ {t} (x) = \ min _ {p} \ {| p |: U (p) {\ text {escrito}} x {\ text {en}} t (| x |) { \ text {passos}} \}}$

Note-se que a complexidade temporal é definida em função da saída x e não do tamanho do programa p. Sipser, em 1983, propôs uma medida do tamanho do menor programa que distingue uma sequência de caracteres x. Buhrman, Fortnow e Laplante em 2002 deram uma versão não determinística, tomando uma máquina universal não determinística. Outras definições podem ser encontradas em Levin , e em Allender onde a definição de complexidade é a soma da complexidade de Kolmogorov e a contribuição da complexidade do tempo.

Link com a teoria da complexidade algorítmica

As ligações entre a complexidade de Kolmogorov e a teoria da complexidade foram estabelecidas usando o seguinte conjunto como um oráculo :

R = conjunto de cadeias de caracteres x cuja complexidade de Kolmogorov é pelo menos | x | / 2

Em 2002, Allender Buhrman, Koucky van Melkebeek e Ronnerbuger mostram que PSPACE está incluído no P R e EXPTIME está incluído em NP R . Então, em 2004, Allender Buhrman, Koucky demonstrar, usando as mesmas técnicas que nexptime está incluído no NP R .

Notas e referências

Parte deste artigo (ou de uma versão anterior) foi adaptada de " Pequeno manual para o uso de agregados preparando a modelagem oral de estocástica ", escrito por Djèlil Chafaï e publicado sob GFDL .

Notas

Referências

Andrey Kolmogorov , “ On Tables of Random Numbers ”, Sankhyā Ser. A. , vol. 25,1963, p. 369-375 ( revisões de matemática 178484 )
Andrey Kolmogorov , “ On Tables of Random Numbers, ” Theoretical Computer Science , vol. 207, n o 21998, p. 387-395 ( DOI 10.1016 / S0304-3975 (98) 00075-9 , Math Reviews 1643414 )
Página de descrição do arquivo no Wikimedia Commons .
(en-GB) Osamu Watanabe , Kolmogorov Complexity and Computational Complexity , col. "Monografias EATCS em Ciência da Computação Teórica",1992( ISBN 978-3-642-77737-0 , DOI 10.1007 / 978-3-642-77735-6 , leia online )
Michael Sipser , " A Complexity Theoretic Approach to Randomness ", Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing , ACM, sTOC '83,1983, p. 330–335 ( ISBN 9780897910996 , DOI 10.1145 / 800061.808762 , lido online , acessado em 14 de julho de 2019 )
H. Buhrman , L. Fortnow e S. Laplante , “ Resource-Bounded Kolmogorov Complexity Revisited ”, SIAM Journal on Computing , vol. 31, n o 3,1 ° de janeiro de 2001, p. 887–905 ( ISSN 0097-5397 , DOI 10.1137 / S009753979834388X , ler online , acessado em 14 de julho de 2019 )
Eric Allender , " When Worlds Collide: Derandomization, Lower Bounds, and Kolmogorov Complexity ", Of Reductions, em "proc.29thacm Symposium on Theory of Computing ,1997, p. 730–738 ( ler online , acessado em 14 de julho de 2019 )
E. Allender , H. Buhrman , M. Koucky e D. van Melkebeek , “ Power from random strings ”, The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. ,Novembro de 2002, p. 669-678 ( DOI 10.1109 / SFCS.2002.1181992 , ler online , acessado em 14 de julho de 2019 )
(em) Eric Allender , Harry Buhrman e Michal Koucký , " O que pode ser eficientemente reduzido às cordas K-Random? » , STACS 2004 , Springer Berlin Heidelberg, lecture Notes in Computer Science,2004, p. 584-595 ( ISBN 9783540247494 , DOI 10.1007 / 978-3-540-24749-4_51 , lido online , acessado em 14 de julho de 2019 )

Apêndices

Bibliografia

(fr) Gregory Chaitin Chance and complex in mathematics, the quest for Ω , Flammarion, janeiro de 2007 ( ISBN 2082105687 ) .
Ming Li e Paul Vitanyi. Uma introdução à complexidade de Kolmogorov e suas aplicações. Springer Verlag 2008 ( ISBN 978-0-387-49820-1 )