Complexidade de Kolmogorov

A complexidade de Kolmogorov tem sua origem nos anos 1960, quando Andrei Kolmogorov, Ray Solomonoff e Gregory Chaitin desenvolveram, de forma independente, uma teoria da informação baseada no tamanho dos programas para a Máquina de Turing. Convencionou-se chamar a área genericamente de "complexidade de Kolmogorov" em homenagem ao famoso matemático russo, e fundador da área, Andrei Nikolaevich Kolmogorov (1903-1987).

A complexidade de Kolmogorov está definida sobre o conjunto de strings binárias (seqüências de zeros e uns). Ela associa a cada string binária um valor numérico que é sua "complexidade". A complexidade de Kolmogorov pode ser definida simplificadamente como o tamanho do menor programa (ou descrição algoritmica) que computa na Máquina de Turing uma determinada string binária. Exige-se que o conjunto de descrições (programas) forme um conjunto livre de prefixo, e se chama esta complexidade de "complexidade de prefixo", representada por K ( x ) {\displaystyle K(x)} . Para enfatizar a Máquina que está sendo usada para definir a complexidade podemos escrever K M ( x ) {\displaystyle K_{M}(x)} ao invés de K ( x ) {\displaystyle K(x)} , onde M {\displaystyle M} é uma Máquina de Turing em particular. Também podemos definir uma complexidade condicional, K ( x | y ) {\displaystyle K(x|y)} , definida como o tamanho do programa que computa x {\displaystyle x} a partir de y {\displaystyle y} , que é dado como entrada do programa. Intuitivamente, K ( x | y ) {\displaystyle K(x|y)} representa a quantidade de informação que devemos adicionar à informação em y {\displaystyle y} para computar x {\displaystyle x} .

A Máquina de Turing é um dispositivo que foi proposto em 1936 por Alan Turing com o objetivo de formalizar matematicamente o que entendemos por "computador". Ela é basicamente formada por uma fita na qual um cabeçote pode escrever símbolos de um conjunto pré-definido, e assim cálculos de diversos tipos podem ser feitos apenas com os movimentos deste cabeçote sobre a fita. Uma propriedade importante da Máquina de Turing é a universalidade, ou seja, a capacidade da Máquina de Turing de simular qualquer outra máquina. Por isto, podemos chama-la de máquina universal.

Da forma como foi definido, pode parecer que a complexidade de Kolmogorov permanece dependente da máquina escolhida como máquina de referência. No entanto, existe um teorema (chamado Teorema da Invariância) que prova que todas as máquinas universais (ou seja, que tem a capacidade de simular todas as outras máquinas de Turing concebíveis) resultam no mesmo valor de complexidade, a não ser por uma constante que é assintoticamente desprezável: K U 1 ( x ) ≤ K U 2 ( x ) + c {\displaystyle K_{U1}(x)\leq K_{U2}(x)+c} , para alguma constante c {\displaystyle c} , e U 1 {\displaystyle U1} e U 2 {\displaystyle U2} são duas máquinas universais quaisquer. Isto significa que a complexidade passa a ser um atributo intrínseco do objeto, independente da máquina universal escolhida como máquina de referência.

Ao medir a complexidade de uma string pelo tamanho do menor programa, a complexidade de Kolmogorov reedita um antigo princípio, de autoria de William de Ockham (1285?-1349?), que ficou conhecido como Navalha de Occam, que diz que "entidades não devem ser multiplicadas desnecessariamente". O Princípio de Occam significa que entre todas as teorias que representam um fenômeno, a mais simples (ou menor) é a melhor para este fim. Isto tem evidentes conotações filosóficas relacionadas com a expressividade dos métodos de descrição e com os sistemas formais.

Trivialmente, K ( x ) ≤ | x | + c {\displaystyle K(x)\leq |x|+c} , para algum c {\displaystyle c} , onde | x | {\displaystyle |x|} denota o tamanho da string x {\displaystyle x} , já que qualquer string pode ser computada por um programa que a tem armazenada literalmente no programa. Também sabemos que K ( x | y ) ≤ K ( x ) + c {\displaystyle K(x|y)\leq K(x)+c} , já que, na complexidade condicional, a presença de y {\displaystyle y} é uma informação a mais que é fornecida ao programa que computará x {\displaystyle x} . Se x {\displaystyle x} denota uma string binária que é resultado de um p {\displaystyle p} -processo de Bernoulli, então 1 n K ( x ) → H ( p , 1 − p ) {\displaystyle {\frac {1}{n}}K(x)\rightarrow H(p,1-p)} em probabilidade, onde H ( p , 1 − p ) {\displaystyle H(p,1-p)} é a entropia do processo. Isto significa que K ( x ) {\displaystyle K(x)} é assintoticamente convergente à entropia da teoria da informação clássica.

Se para uma string binária x {\displaystyle x} , K ( x ) ≥ | x | − c {\displaystyle K(x)\geq |x|-c} , para algum c {\displaystyle c} , então dizemos que x {\displaystyle x} é incompressível. Kolmogorov associou o conceito de incompressividade com o conceito de aleatoriedade, com o objetivo de definir seqüências aleatórias, e assim fornecer uma base teórica para probabilidades e estatística.

O objetivo original do trabalho de Kolmogorov era obter uma definição formal de seqüência aleatória. Kolmogorov observou que algumas seqüências binárias podiam ser comprimidas algoritmicamente. Nos dias de hoje, a maioria das pessoas está acostumada a usar programas de compressão de dados, tais como winzip, gzip, arj, etc. Assim, a ideia que dados possam ser comprimidos não é de todo estranha. Fica fácil perceber que um número como 1.000.000.000 na base 10 pode ser facilmente expresso como 10 9 {\displaystyle 10^{9}} , enquanto que o número 5.321.478.927, escolhido arbitrariamente, não poderia ser expresso desta forma compacta. Se tomarmos as strings binárias 11111111111111111111 e 10110011010111011010, aceitaríamos facilmente a segunda como sendo resultante do lançamento sucessivo de uma moeda honesta (1=cara e 0=coroa). No entanto, dificilmente a primeira seqüência poderia ser resultado de um experimento realmente aleatório. Notamos que a primeira string poderia ser computada pelo programa:

A razão para exigir que o conjunto de descrições (programas) forme um conjunto livre de prefixo deve-se a desigualdade de Kraft, expressão bem conhecida na teoria da informação clássica. Ela significa que a série ∑ 2 − K ( x ) {\displaystyle \sum 2^{-K(x)}} converge. Esta é uma propriedade importante da complexidade de Kolmogorov.

Uma resposta consistente ao problema de definir o conceito de seqüência aleatória foi dada por Per Martin-Löf. A definição de Martin-Löf baseia-se em teoria da medida, e na existência de um conjunto efetivo nulo maximal, no conjunto das strings binárias. Isto significa a existência de um conjunto nulo (com baixa probabilidade de ocorrência) que contém todos os conjuntos nulos cujas strings podem ser algoritmicamente geradas. Esta definição equivale a afirmar a existência de um teste de aleatoriedade universal. Interessante observar que a definição de Martin-Löf é equivalente à definição de seqüência aleatória dada pela complexidade de Kolmogorov (via incompressividade das strings).