Algoritmisk komplexitet, (beräkningskomplexitet, eller Kolmogorov-komplexitet), är en grundläggande idé i både beräkningskomplexitetsteori och algoritmisk informationsteori, och spelar en viktig roll i formell induktion.
Den algoritmiska komplexiteten hos en binär sträng definieras som det kortaste och mest effektiva programmet som kan producera strängen. Även om det finns ett oändligt antal program som kan producera vilken sträng som helst, kommer ett program eller en grupp av program alltid att vara den kortaste. Det finns inget algoritmiskt sätt att hitta den kortaste algoritmen som matar ut en given sträng; detta är ett av de första resultaten av beräkningskomplexitetsteorin. Trots det kan vi göra en kvalificerad gissning. Detta resultat, (en strängs beräkningskomplexitet), visar sig vara mycket viktigt för bevis relaterade till beräkningsbarhet.
Eftersom alla fysiska objekt eller egenskaper i princip kan beskrivas till nästan utmattning av en sträng av bitar, kan objekt och egenskaper också sägas ha algoritmisk komplexitet. Faktum är att att reducera komplexiteten hos verkliga objekt till program som producerar objekten som utdata, är ett sätt att se på vetenskapens företag. De komplexa objekten runt omkring oss tenderar att komma från tre huvudsakliga genereringsprocesser; uppkomst, evolution och intelligens, där objekten som produceras av var och en tenderar mot större algoritmisk komplexitet.
Beräkningskomplexitet är ett begrepp som ofta används inom teoretisk datavetenskap för att bestämma den relativa svårigheten att beräkna lösningar på breda klasser av matematiska och logiska problem. Mer än 400 komplexitetsklasser finns, och ytterligare klasser upptäcks kontinuerligt. Den berömda P = NP-frågan gäller karaktären hos två av dessa komplexitetsklasser. Komplexitetsklasser inkluderar problem som är mycket svårare än något man kan ställas inför i matematik upp till kalkyl. Det finns många tänkbara problem inom beräkningskomplexitetsteorin som skulle kräva nästan oändlig tid att lösa.
Algoritmisk komplexitet och relaterade koncept utvecklades på 1960-talet av dussintals forskare. Andrey Kolmogorov, Ray Solomonoff och Gregory Chaitin gjorde viktiga bidrag i slutet av 60-talet med algoritmisk informationsteori. Principen om minsta meddelandelängd, nära relaterad till algoritmisk komplexitet, utgör mycket av grunden för statistisk och induktiv slutledning och maskininlärning.