Algoritemska kompleksnost (računalniška kompleksnost ali kompleksnost Kolmogorova) je temeljna ideja tako v teoriji računske kompleksnosti kot v teoriji algoritemskih informacij in ima pomembno vlogo pri formalni indukciji.
Algoritemska kompleksnost binarnega niza je opredeljena kot najkrajši in najučinkovitejši program, ki lahko proizvede niz. Čeprav obstaja neskončno število programov, ki lahko ustvarijo kateri koli dani niz, bo en program ali skupina programov vedno najkrajša. Ni algoritemskega načina za iskanje najkrajšega algoritma, ki izpiše dani niz; to je eden prvih rezultatov teorije zapletenosti računanja. Kljub temu lahko ugibamo. Ta rezultat (računska kompleksnost niza) se izkaže za zelo pomembnega za dokaze, povezane z izračunljivostjo.
Ker je vsak fizični objekt ali lastnost načeloma mogoče opisati do skoraj izčrpanja z nizom bitov, lahko rečemo, da imajo tudi objekte in lastnosti algoritemsko kompleksnost. Pravzaprav je zmanjševanje kompleksnosti predmetov iz resničnega sveta na programe, ki predmete proizvajajo kot izhod, eden od načinov gledanja na podjetništvo znanosti. Kompleksni predmeti okoli nas ponavadi izhajajo iz treh glavnih generacijskih procesov; nastanek, evolucija in inteligenca, pri čemer se objekti, ki jih vsak proizvede, težijo k večji algoritemski kompleksnosti.
Računalniška kompleksnost je pojem, ki se pogosto uporablja v teoretični računalniški znanosti za določitev relativne težavnosti računanja rešitev širokih razredov matematičnih in logičnih problemov. Obstaja več kot 400 kompleksnih razredov, dodatne razrede pa nenehno odkrivamo. Znamenito vprašanje P = NP se nanaša na naravo dveh od teh razredov kompleksnosti. Kompleksni razredi vključujejo probleme, ki so veliko težji od vseh, s katerimi bi se lahko soočili v matematiki do računanja. V teoriji zapletenosti računanja obstaja veliko predstavljivih problemov, za reševanje katerih bi bilo potrebno skoraj neskončno količino časa.
Algoritemsko kompleksnost in povezane koncepte je v šestdesetih letih prejšnjega stoletja razvilo na desetine raziskovalcev. Andrey Kolmogorov, Ray Solomonoff in Gregory Chaitin so v poznih 1960. letih prejšnjega stoletja pomembno prispevali k algoritemski informacijski teoriji. Načelo minimalne dolžine sporočila, tesno povezano z algoritemsko kompleksnostjo, zagotavlja velik del temeljev statističnega in induktivnega sklepanja ter strojnega učenja.