Complexitatea algoritmică, (complexitatea computațională sau complexitatea Kolmogorov), este o idee fundamentală atât în teoria complexității computaționale, cât și în teoria informației algoritmice și joacă un rol important în inducerea formală.
Complexitatea algoritmică a unui șir binar este definită ca cel mai scurt și mai eficient program care poate produce șirul. Deși există un număr infinit de programe care pot produce orice șir dat, un program sau un grup de programe va fi întotdeauna cel mai scurt. Nu există o modalitate algoritmică de a găsi cel mai scurt algoritm care scoate un șir dat; acesta este unul dintre primele rezultate ale teoriei complexității computaționale. Chiar și așa, putem face o presupunere educată. Acest rezultat, (complexitatea de calcul a unui șir), se dovedește a fi foarte important pentru dovezile legate de calculabilitate.
Deoarece orice obiect sau proprietate fizică poate fi descrisă în principiu până la aproape epuizare printr-un șir de biți, se poate spune că obiectele și proprietățile au și complexitate algoritmică. De fapt, reducerea complexității obiectelor din lumea reală la programe care produc obiectele ca rezultat, este o modalitate de a vedea întreprinderea științei. Obiectele complexe din jurul nostru tind să provină din trei procese generatoare principale; apariția, evoluția și inteligența, obiectele produse de fiecare tinzând spre o mai mare complexitate algoritmică.
Complexitatea computațională este o noțiune folosită frecvent în informatica teoretică pentru a determina dificultatea relativă a calculării soluțiilor la clase largi de probleme matematice și logice. Există peste 400 de clase de complexitate, iar clase suplimentare sunt descoperite în mod continuu. Celebra întrebare P = NP se referă la natura a două dintre aceste clase de complexitate. Clasele de complexitate includ probleme mult mai dificile decât orice s-ar putea confrunta în matematică până la calcul. Există multe probleme imaginabile în teoria complexității computaționale care ar necesita o perioadă aproape infinită de timp pentru a fi rezolvate.
Complexitatea algoritmică și conceptele conexe au fost dezvoltate în anii 1960 de zeci de cercetători. Andrey Kolmogorov, Ray Solomonoff și Gregory Chaitin au adus contribuții importante la sfârșitul anilor ’60 cu teoria informației algoritmice. Principiul lungimii minime a mesajului, strâns legat de complexitatea algoritmică, oferă o mare parte din temelia inferenței statistice și inductive și a învățării automate.