complessità algoritmica, (complessità computazionale, o la complessità di Kolmogorov), è un concetto fondamentale in entrambi i teoria della complessità computazionale e teoria dell'informazione algoritmica , e svolge un ruolo importante nella formazione induzione.

La complessità algoritmica di una stringa binaria è definito come il programma più breve ed efficace che può produrre la stringa. Anche se ci sono un numero infinito di programmi che possono produrre qualsiasi stringa, un programma o di un gruppo di programmi sarà sempre più breve. Non c'è modo algoritmico di trovare l'algoritmo più breve, che genera una stringa data, questo è uno dei primi risultati della teoria della complessità computazionale. Anche così, siamo in grado di formulare un'ipotesi. Questo risultato, (la complessità computazionale di una stringa), risulta essere molto importante per le prove relative alla computabilità.

Dal momento che ogni oggetto fisico o la proprietà può essere descritto in linea di principio a quasi esaurimento da una stringa di bit, oggetti e proprietà si può dire di avere la complessità algoritmica pure. In effetti, riducendo la complessità di oggetti del mondo reale ai programmi che producono gli oggetti come produzione, è un modo di concepire l'impresa della scienza. Gli oggetti complessi che ci circondano tendono a provenire da tre principali processi di generazione; emergere , evoluzione , e , con gli oggetti prodotti da ciascuno tendente una maggiore complessità algoritmica.

complessità computazionale è un concetto spesso usato in informatica teorica per determinare la relativa difficoltà di calcolare le soluzioni alle classi gamma di problemi matematici e logici. Più di 400 classi di complessità esiste, e le classi aggiuntive vengono continuamente scoperte. Il famoso P=NP discussione la natura di due di queste classi di complessità. Classi di complessità sono problemi molto più difficile di quanto si possa affrontare qualsiasi cosa in matematica fino al calcolo. Ci sono molti problemi immaginabili in teoria della complessità computazionale, che richiederebbe una quantità quasi infinita di tempo per risolvere.

complessità algoritmica e concetti relativi sono stati sviluppati nel 1960 da decine di ricercatori. Andrey Kolmogorov, Ray Solomonoff e Gregory Chaitin dato un contributo importante nella fine degli anni '60 con la teoria dell'informazione algoritmica. Il principio di minima lunghezza del messaggio, in stretta relazione alla complessità algoritmica, fornisce la maggior parte della fondazione di inferenza statistica e di apprendimento induttivo e macchina.