Complexidade de Kolmorogov
Complexidade de Kolmogorov, também conhecida como complexidade algorítmica da informação, é uma medida da quantidade de informações contidas em uma cadeia de caractere. É definida como a extensão do programa mais curto possível que pode ser escrito em uma linguagem de programação para gerar uma determinada cadeia de caracteres. Em outras palavras, é uma medida (proporcional) da quantidade mínima de informação necessária para descrever uma cadeia de caracteres.
É baseado na ideia de que se uma dada sequência S pode ser gerada por um algoritmo menor que o comprimento da sequência dada, então S pode ser considerada uma sequência aleatória. A ideia básica é que qualquer sequência de caracteres pode ser comprimida em sua forma mais eficiente e a complexidade Kolmogorov de uma sequência é do tamanho do programa mais curto necessário para gerar essa sequência, ou a Descrição de Menor Comprimento (do inglês Mininum Description Length).
Essa abordagem fornece uma medida teórica da quantidade de informação contida em uma cadeia de caracteres e pode ser usada para comparar a complexidade de diferentes cadeias de caracteres. Entretanto, é importante notar que a complexidade do Kolmogorov não é uma medida prática e não pode ser computada diretamente (em termos numéricos) para uma determinada cadeia de caracteres.
Por exemplo, considere a cadeia de caracteres "olá mundo", esta cadeia de caracteres (de tamanho 9) pode ser gerada por um programa que simplesmente imprime os caracteres "olá mundo" na tela. A complexidade Kolmogorov desta cadeia teria o mesmo comprimento deste programa (que é relativamente curto).
Por outro lado, considere uma cadeia que contenha uma abundância de dados aleatórios. A complexidade Kolmogorov desta cadeia de caracteres seria muito maior, porque exigiria um programa mais longo para gerá-la. Em geral, as cadeias com alta complexidade de Kolmogorov são consideradas mais complexas e contêm mais informações do que as cadeias com baixa complexidade.
Outro exemplo muito interessante é o do número pi, ele é um número irracional com infinitas casas decimais, porém existem algoritmos que conseguem gerar quantas casa decimais forem solicitadas com baixo erro e esses algoritmos possuem relativa simplicidade, como o dos irmãos David e Gregory Chudnovsky [1].
Para entender este conceito mais claramente, vamos olhar para um exemplo em que é possível comprimir uma cadeia. Vamos supor que temos duas cadeias de tamanho n=8:
A primeira cadeia x = 01010101
A segunda cadeia x' = 11101001
Para a primeira cadeia, podemos criar um programa de tamanho 4 (ou n/2) que irá gerá-la. Baseado no python, o programa poderia ser algo parecido com isto:
print("01"*4)
Porém, para a segunda cadeia nós teremos algo como a impressão da própria cadeia de caracteres:
print("11101001")
Agora podemos definir um conjunto de strings aleatórias, R, como se segue:
R = {x|K(x) ≥ |x|}
Neste caso, uma cadeia é considerada aleatória se o tamanho do menor programa que a pode gerar for maior ou igual ao tamanho da própria cadeia. Esta definição de aleatoriedade pode ser bastante satisfatória, pois demonstra que uma cadeia de caracteres é aleatória se não conseguirmos criar um padrão inteligente para descrevê-la ou gerá-la.
No entanto, esta noção de aleatoriedade acaba se tornando fundamentalmente problemática. Acontece que não é possível chegar a um algoritmo geral para encontrar este conjunto R e determinar se um dado x é aleatório. Este resultado é conhecido como o teorema da Incompletude de Kolmogorov.
A complexidade do Kolmogorov é um conceito muito importante para à ciência de dados e para a teoria da informação. Ele pode ser usado para classificar os dados em termos de complexidade. A compreensão deste conceito pode ajudar os cientistas de dados a tomar melhores decisões quando se trata de comprimir dados ou criar algoritmos para gerar esses dados.
[1] https://brasil.elpais.com/brasil/2018/03/14/ciencia/1521011921_905686.html
[3] https://homepages.cwi.nl/~paulv/papers/handbooklogic07.pdf
