Algoritminen monimutkaisuus (laskennallinen monimutkaisuus tai Kolmogorovin monimutkaisuus) on perusidea sekä laskennallisen monimutkaisuuden teoriassa että algoritmisessa informaatioteoriassa, ja sillä on tärkeä rooli muodollisessa induktiossa.
Binäärisen merkkijonon algoritminen monimutkaisuus määritellään lyhimmäksi ja tehokkaimmaksi ohjelmaksi, joka voi tuottaa merkkijonon. Vaikka on olemassa ääretön määrä ohjelmia, jotka voivat tuottaa minkä tahansa merkkijonon, yksi ohjelma tai ohjelmaryhmä on aina lyhin. Ei ole algoritmista tapaa löytää lyhin algoritmi, joka antaa annetun merkkijonon; tämä on yksi laskennallisen monimutkaisuusteorian ensimmäisistä tuloksista. Siitä huolimatta voimme tehdä koulutetun arvauksen. Tämä tulos (merkkijonon laskennallinen monimutkaisuus) osoittautuu erittäin tärkeäksi laskettavuuteen liittyvien todisteiden kannalta.
Koska mikä tahansa fyysinen esine tai ominaisuus voidaan periaatteessa kuvata lähes tyhjäksi bittisarjalla, voidaan myös objektien ja ominaisuuksien sanoa olevan algoritmisesti monimutkaisia. Todellisten kohteiden monimutkaisuuden vähentäminen ohjelmiksi, jotka tuottavat esineitä tuotoksena, on itse asiassa yksi tapa tarkastella tieteen yritystä. Ympärillämme olevat monimutkaiset esineet tulevat yleensä kolmesta pääprosessista; syntymistä, evoluutiota ja älykkyyttä, ja kunkin tuottamat objektit pyrkivät lisäämään algoritmista monimutkaisuutta.
Laskennallinen monimutkaisuus on käsite, jota käytetään usein teoreettisessa tietojenkäsittelytieteessä määritettäessä suhteellisia vaikeuksia laskea ratkaisuja laajaan joukkoon matemaattisia ja loogisia ongelmia. On olemassa yli 400 monimutkaisuusluokkaa, ja uusia luokkia löydetään jatkuvasti. Kuuluisa P = NP -kysymys koskee kahden monimutkaisuusluokan luonnetta. Monimutkaisuusluokat sisältävät ongelmia, jotka ovat paljon vaikeampia kuin mikään, mitä matematiikassa voisi kohdata laskelmiin asti. Laskennallisen monimutkaisuuden teoriassa on monia kuviteltavissa olevia ongelmia, joiden ratkaiseminen vaatisi lähes äärettömän paljon aikaa.
Kymmenet tutkijat ovat kehittäneet algoritmiset monimutkaisuudet ja niihin liittyvät käsitteet 1960 -luvulla. Andrey Kolmogorov, Ray Solomonoff ja Gregory Chaitin antoivat tärkeän panoksen 60 -luvun lopulla algoritmisen tiedon teorian avulla. Sanomien vähimmäispituuden periaate, joka liittyy läheisesti algoritmisiin monimutkaisuuksiin, tarjoaa suuren osan tilastollisen ja induktiivisen johtopäätöksen ja koneoppimisen perustasta.