Che cos'è la complessità algoritmica?
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 ci sia un numero infinito di programmi in grado di produrre una determinata stringa, un programma o un gruppo di programmi sarà sempre il più breve. Non esiste un modo algoritmico per trovare l'algoritmo più breve che genera una determinata stringa; questo è uno dei primi risultati della teoria della complessità computazionale. Anche così, possiamo fare un'ipotesi colta. Questo risultato, (la complessità computazionale di una stringa), risulta essere molto importante per le prove relative alla calcolabilità.
Poiché in linea di principio qualsiasi oggetto fisico o proprietà può essere descritto come quasi esaurimento da una serie 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 oggetti come output, è un modo di vedere l'impresa della scienza. Gli oggetti complessi intorno a noi tendono a provenire da tre principali processi di generazione; emergenza , evoluzione e intelligenza , con gli oggetti prodotti da ciascuno tendendo verso una maggiore complessità algoritmica.
La complessità computazionale è una nozione frequentemente usata 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 ulteriori classi vengono continuamente scoperte. 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à quasi infinita di tempo per risolvere.
Decine di ricercatori hanno sviluppato complessità algoritmica e concetti correlati negli anni '60. Andrey Kolmogorov, Ray Solomonoff e Gregory Chaitin hanno dato importanti contributi alla fine degli anni '60 con la teoria dell'algoritmo dell'informazione. 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.