O que é complexidade algorítmica?

A complexidade algorítmica

, (complexidade computacional, ou complexidade Kolmogorov), é uma idéia fundamental na teoria da complexidade computacional e teoria da informação algorítmica e desempenha um papel importante na indução formal.

A complexidade algorítmica de uma sequência binária é definida como o programa mais curto e mais eficiente que pode produzir a string. Embora exista um número infinito de programas que possam produzir qualquer string, 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 gera uma determinada sequência; Este é um dos primeiros resultados da teoria da complexidade computacional. Mesmo assim, podemos fazer um palpite educado. Esse resultado (a complexidade computacional de uma string), acaba sendo muito importante para provas relacionadas à computação.

Como qualquer objeto ou propriedade física pode, em princípioajuda a ter complexidade algorítmica também. De fato, reduzir a complexidade dos objetos do mundo real para programas que produzem os objetos como saída, é uma maneira de visualizar a empresa da ciência. Os objetos complexos ao nosso redor tendem a vir de três processos principais de geração; 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 frequentemente usada na ciência da computação teórica para determinar a dificuldade relativa de calcular 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 p = np questiona diz respeito à natureza de duas dessas classes de complexidade. As aulas de complexidade incluem problemas muito mais difíceis do que qualquer coisaPode enfrentar a matemática até o cálculo. Existem muitos problemas imagináveis ​​na teoria da complexidade computacional que exigiriam uma quantidade de tempo quase infinita para resolver.

A 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 contribuições importantes no final dos anos 60 com a teoria da informação algorítmica. O princípio do comprimento mínimo da mensagem, intimamente relacionado à complexidade algorítmica, fornece grande parte da base de inferência estatística e indutiva e aprendizado de máquina.