Cos'è la complessità algoritmica?

La complessità algoritmica, (complessità computazionale, o complessità di Kolmogorov), è un'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 è definita come il programma più breve ed efficiente che può produrre la stringa.Sebbene ci siano un numero infinito di programmi che possono produrre una determinata stringa, un programma o un gruppo di programmi sarà sempre il più breve.Non esiste un modo algoritmico di trovare l'algoritmo più breve che produce una determinata stringa;Questo è uno dei primi risultati della teoria della complessità computazionale.Anche così, possiamo fare un'ipotesi istruita.Questo risultato, (la complessità computazionale di una stringa), risulta essere molto importante per le prove relative alla calcolabilità.

Poiché qualsiasi oggetto o proprietà fisico può in linea di principio essere descritto in quasi esaustezza da una stringa di bit, oggetti e proprietàSi può dire che abbia anche complessità algoritmica.In effetti, ridurre la complessità degli oggetti del mondo reale a programmi che producono gli oggetti come output, è un modo per visualizzare l'impresa della scienza.Gli oggetti complessi intorno a noi tendono a provenire da tre principali processi di generazione;

Emergence , Evolution e Intelligence , con gli oggetti prodotti da ciascuno che tende verso una maggiore complessità algoritmica.

La complessità computazionale è spesso usata nell'informatica teorica per determinare la difficoltà relativa di calcolare le soluzioni a grandi classi ampiedi problemi matematici e logici.Esistono più di 400 classi di complessità e le classi aggiuntive vengono continuamente scoperte.La famosa domanda

P ' NP riguarda la natura di due di queste classi di complessità.Le lezioni di complessità includono problemi molto più difficili di qualsiasi cosa si possa affrontare in matematica fino al calcolo.Esistono molti problemi immaginabili nella teoria della complessità computazionale che richiederebbero una quantità quasi infinita di tempo per risolvere.

complessità algoritmica e concetti correlati sono stati sviluppati negli anni '60 da dozzine di ricercatori.Andrey Kolmogorov, Ray Solomonoff e Gregory Chaitin hanno dato importanti contributi alla fine degli anni '60 con teoria dell'informazione algoritmica.Il principio della lunghezza minima dei messaggi, strettamente correlato alla complessità algoritmica, fornisce gran parte delle basi di inferenza statistica e induttiva e apprendimento automatico.