Teoria della complessità algoritmica

La teoria della complessità algoritmica o teoria algoritmica della complessità si occupa dello studio della complessità descrittiva degli algoritmi e non delle risorse computazionali (memoria occupata e tempo di calcolo) necessarie ad eseguirli.

Non va, quindi, confusa con la teoria della complessità computazionale.

La teoria algoritmica della complessità è stata sviluppata principalmente da Kolmogorov, Chaitin e Solomonoff, per questo motivo è nota anche come "teoria K-C-S" dalle iniziali dei tre scienziati.

Gli articoli storici dei tre autori sono:

• R.J.Solomonoff, A formal theory of inductive inference. Information and Control, 7:1-22 e 224-254, 1964.
• A.N.Kolmogorov. Three approaches to the quantitative definition of information. Problems of Information Transmission, 1:1-17, 1965.
• G.J.Chaitin. On the length of programs for computing finite binary sequences. Journal of the Association for Computer Machinery, 13:547-569, 1966.

Un testo moderno è il seguente:

• Ming Li and Paul Vitányi, An introduction to Kolmogorov complexity and its applications (2nd ed.), Springer, 1997. ISBN 0-387-94868-6

In italiano:

• Chaitin Gregory J., Alla ricerca di Omega, Adelphi, 2007, ISBN 9788845922053
• Chaitin Gregory J., Teoria algoritmica della complessità, Giappichelli, 2006, ISBN 9788834863985

• Juergen Schmidhuber

• Sito dedicato a Kolmogorov, su kolmogorov.com. URL consultato il 25 ottobre 2007 (archiviato dall'url originale il 15 gennaio 2005).
• Sito di Chaitin, su cs.umaine.edu. URL consultato il 25 ottobre 2007 (archiviato dall'url originale il 15 febbraio 2015).
• Sito di Solomonoff, su idsia.ch.
• Sito di Schmidhuber, su idsia.ch.