Che cosa è Algorithmic Complexity?

Complessità algoritmica, (complessità computazionale, o la complessità di Kolmogorov), è una idea fondamentale sia nella teoria della complessità computazionale e teoria dell'informazione algoritmica, e svolge un ruolo importante nell'induzione formale.

La complessità algoritmica di una stringa binaria è definito come il programma più breve e più efficiente che può produrre la stringa. Anche se ci sono un numero infinito di programmi in grado di produrre ogni stringa, un programma o di un gruppo di programmi sarà sempre più breve. Non c'è modo algoritmico di trovare l'algoritmo più breve che emette una stringa; questo è uno dei primi risultati della teoria della complessità computazionale. Anche così, possiamo fare un'ipotesi. Questo risultato, (la complessità computazionale di una stringa), risulta essere molto importante per prove relative a computability.

Poiché ogni oggetto fisico o proprietà possono in linea di principio essere descritti a quasi esaurimento da una stringa di bit, oggetti e proprietà si può dire di avere la complessità algoritmica pure. Infatti, riducendo la complessità di oggetti reali ai programmi che producono gli oggetti in uscita, è un modo di vedere l'impresa della scienza. Gli oggetti complessi che ci circondano tendono a provenire da tre processi di generazione principali, emergere, evoluzione e intelligenza, con gli oggetti prodotti da ciascuna tende verso una maggiore complessità algoritmica.

Complessità computazionale è un concetto spesso utilizzato in informatica teorica per determinare la relativa difficoltà di calcolare le soluzioni ai ampie classi di problemi matematici e logici. Esistono più di 400 classi di complessità, e vengono continuamente scoperti classi aggiuntive. Il famoso P = NP questione riguarda la natura di due di queste classi di complessità. Classi di complessità sono problemi ben più difficile di qualsiasi cosa si possa affrontare in matematica fino al calcolo. Ci sono molti problemi immaginabili in teoria della complessità computazionale che richiederebbero una quantità pressoché infinita di tempo per risolvere.

Complessità algoritmica e relativi concetti sono stati sviluppati nel 1960 da decine di ricercatori. Andrey Kolmogorov, Ray Solomonoff e Gregory Chaitin reso importanti contributi alla fine degli anni '60 con la teoria dell'informazione algoritmica. Il principio della lunghezza minima messaggio, strettamente legata alla complessità algoritmica, fornisce gran parte della fondazione di inferenza statistica e induttiva e apprendimento automatico.