La complessità algoritmica, (complessità computazionale, o complessità di Kolmogorov), è un’idea fondamentale sia nella teoria della complessità computazionale che nella teoria dell’informazione algoritmica e svolge un ruolo importante nell’induzione formale.
La complessità algoritmica di una stringa binaria è definita come il programma più breve ed efficiente in grado di produrre la stringa. Sebbene esista un numero infinito di programmi in grado di produrre una determinata stringa, un programma o un gruppo di programmi sarà sempre il più corto. Non esiste un modo algoritmico per trovare l’algoritmo più breve che emetta una determinata stringa; questo è uno dei primi risultati della teoria della complessità computazionale. Anche così, possiamo fare un’ipotesi plausibile. Questo risultato, (la complessità computazionale di una stringa), risulta essere molto importante per le dimostrazioni relative alla computabilità.
Poiché qualsiasi oggetto fisico o proprietà può in linea di principio essere descritto fino all’esaurimento da una stringa di bit, si può dire che anche oggetti e proprietà hanno complessità algoritmica. In effetti, ridurre la complessità degli oggetti del mondo reale a programmi che producono gli oggetti come output, è un modo di vedere l’impresa della scienza. Gli oggetti complessi che ci circondano tendono a provenire da tre principali processi di generazione; emergenza, evoluzione e intelligenza, con gli oggetti prodotti da ciascuno tendenti a una maggiore complessità algoritmica.
La complessità computazionale è una nozione frequentemente utilizzata nell’informatica teorica per determinare la relativa difficoltà di calcolare le soluzioni ad ampie classi di problemi matematici e logici. Esistono più di 400 classi di complessità e vengono continuamente scoperte classi aggiuntive. La famosa domanda P = NP riguarda la natura di due di queste classi di complessità. Le classi di complessità includono problemi molto più difficili di qualsiasi cosa si possa affrontare in matematica fino al calcolo. Ci sono molti problemi immaginabili nella teoria della complessità computazionale che richiederebbero una quantità di tempo quasi infinita per essere risolti.
La complessità algoritmica e i relativi concetti sono stati sviluppati negli anni ‘1960 da dozzine di ricercatori. Andrey Kolmogorov, Ray Solomonoff e Gregory Chaitin hanno dato importanti contributi alla fine degli anni ’60 con la teoria dell’informazione algoritmica. Il principio della lunghezza minima del messaggio, strettamente correlato alla complessità algoritmica, fornisce gran parte delle basi dell’inferenza statistica e induttiva e dell’apprendimento automatico.