O que é Complexidade Algorítmica?
A complexidade algorítmica (complexidade computacional ou complexidade Kolmogorov) é uma idéia fundamental na teoria da complexidade computacional e na teoria da informação algorítmica e desempenha um papel importante na indução formal.
A complexidade algorítmica de uma string binária é definida como o programa mais curto e mais eficiente que pode produzir a string. Embora haja um número infinito de programas que podem produzir qualquer sequência, um programa ou grupo de programas sempre será o mais curto. Não existe uma maneira algorítmica de encontrar o algoritmo mais curto que produz uma determinada string; este é um dos primeiros resultados da teoria da complexidade computacional. Mesmo assim, podemos adivinhar. Esse resultado (a complexidade computacional de uma string) acaba sendo muito importante para provas relacionadas à computabilidade.
Como qualquer objeto ou propriedade física pode, em princípio, ser descrita como quase esgotada por uma sequência de bits, pode-se dizer que objetos e propriedades têm complexidade algorítmica. De fato, reduzir a complexidade de objetos do mundo real a programas que produzem os objetos como saída, é uma maneira de ver a empresa da ciência. Os objetos complexos ao nosso redor tendem a vir de três processos geradores principais; emergência , evolução e inteligência , com os objetos produzidos por cada um tendendo a uma maior complexidade algorítmica.
A complexidade computacional é uma noção freqüentemente usada na ciência da computação teórica para determinar a dificuldade relativa de computar as soluções para grandes classes de problemas matemáticos e lógicos. Existem mais de 400 classes de complexidade e classes adicionais estão sendo descobertas continuamente. A famosa questão P = NP diz respeito à natureza de duas dessas classes de complexidade. As classes de complexidade incluem problemas muito mais difíceis do que qualquer coisa que se possa enfrentar em matemática até o cálculo. Existem muitos problemas imagináveis na teoria da complexidade computacional que exigiriam uma quantidade quase infinita de tempo para serem resolvidos.
Complexidade algorítmica e conceitos relacionados foram desenvolvidos na década de 1960 por dezenas de pesquisadores. Andrey Kolmogorov, Ray Solomonoff e Gregory Chaitin fizeram importantes contribuições no final dos anos 60 com a teoria algorítmica da informação. O princípio do tamanho mínimo da mensagem, intimamente relacionado à complexidade algorítmica, fornece grande parte dos fundamentos da inferência estatística e indutiva e do aprendizado de máquina.