¿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 y 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 existe 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 físico o propiedad puede describirse, en principioayuda para tener complejidad algorítmica también. De hecho, reducir la complejidad de los objetos del mundo real a los 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; emergencia , evolución y inteligencia , con los objetos producidos por cada uno que tenden hacia una mayor complejidad algorítmica.
La complejidad computacional es una noción utilizada con frecuencia en la informática teórica para determinar la dificultad relativa de calcular las soluciones a amplias clases de problemas matemáticos y lógicos. Existen más de 400 clases de complejidad, y se descubren continuamente 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 cosapodría confrontar 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 infinito 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.