Cos'è la complessità algoritmica?
La complessità algoritmica
(complessità computazionale o complessità di Kolmogorov), è un'idea fondamentale sia nella teoria della complessità computazionale che in 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 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 modo quasi esaustivo da una stringa di bit, oggetti e proprietàAiuto ad avere 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 a una maggiore complessità algoritmica.
La complessità computazionale è una nozione frequentemente utilizzata nell'informatica teorica per determinare la difficoltà relativa di calcolare le soluzioni a ampie classi di 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 cosapotrebbe confrontarsi in matematica fino al calcolo. Ci sono molti problemi immaginabili nella teoria della complessità computazionale che richiederebbero un tempo quasi infinito 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.