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 una cantidad infinita 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 genere una cadena determinada; este es uno de los primeros resultados de la teoría de la complejidad computacional. Aun así, podemos hacer una suposición fundamentada. 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, en principio, describirse hasta el agotamiento mediante una cadena de bits, se puede decir que los objetos y propiedades también tienen una 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; emergencia, evolución e inteligencia, con los objetos producidos por cada uno tendiendo a una mayor complejidad algorítmica.
La complejidad computacional es una noción que se utiliza 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 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 cálculo. Hay muchos problemas imaginables en la teoría de la complejidad computacional que requerirían una cantidad de tiempo casi infinita para resolverse.
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 60 con la teoría algorítmica de la información. El principio de 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.