¿Qué es la complejidad algorítmica?

La complejidad algorítmica (complejidad computacional o complejidad de Kolmogorov) es una idea fundamental tanto en la teoría de la complejidad computacional como en la teoría de la información algorítmica , y juega un papel importante en la inducción formal.

La complejidad algorítmica de una cadena binaria se define como el programa más corto y eficiente que puede producir la cadena. Aunque hay un número infinito de programas que pueden producir cualquier cadena dada, un programa o grupo de programas siempre será el más corto. No hay una forma algorítmica de encontrar el algoritmo más corto que genera una cadena dada; Este es uno de los primeros resultados de la teoría de la complejidad computacional. Aun así, podemos hacer una suposición educada. Este resultado, (la complejidad computacional de una cadena), resulta ser muy importante para las pruebas relacionadas con la computabilidad.

Dado que cualquier objeto o propiedad física puede describirse, en principio, casi hasta el agotamiento por una cadena de bits, se puede decir que los objetos y propiedades también tienen complejidad algorítmica. De hecho, reducir la complejidad de los objetos del mundo real a programas que producen los objetos como salida, es una forma de ver la empresa de la ciencia. Los objetos complejos que nos rodean tienden a provenir de tres procesos generadores principales; surgimiento , evolución e inteligencia , con los objetos producidos por cada uno tendiendo hacia una mayor complejidad algorítmica.

La complejidad computacional es una noción frecuentemente utilizada en la informática teórica para determinar la dificultad relativa de computar las soluciones a amplias clases de problemas matemáticos y lógicos. Existen más de 400 clases de complejidad y continuamente se descubren clases adicionales. La famosa pregunta P = NP se refiere a la naturaleza de dos de estas clases de complejidad. Las clases de complejidad incluyen problemas mucho más difíciles que cualquier cosa que uno pueda enfrentar en matemáticas hasta el cálculo. Hay muchos problemas imaginables en la teoría de la complejidad computacional que requerirían una cantidad de tiempo casi infinita para resolver.

La complejidad algorítmica y los conceptos relacionados fueron desarrollados en la década de 1960 por docenas de investigadores. Andrey Kolmogorov, Ray Solomonoff y Gregory Chaitin hicieron importantes contribuciones a finales de los años 60 con la teoría de la información algorítmica. El principio de la longitud mínima del mensaje, estrechamente relacionado con la complejidad algorítmica, proporciona gran parte de la base de la inferencia estadística e inductiva y el aprendizaje automático.