Vad är algoritmisk komplexitet?

Algoritmisk komplexitet (beräkningskomplexitet, eller Kolmogorov-komplexitet), är en grundidé i både beräkningskomplexitetsteori och algoritmisk informationsteori , och spelar en viktig roll i formell induktion.

Den algoritmiska komplexiteten för 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 en given sträng, kommer ett program eller en grupp program alltid att vara det 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 från beräkningskomplexitetsteorin. Trots det kan vi göra en utbildad gissning. Detta resultat (en strängs beräkningskomplexitet) visar sig vara mycket viktigt för bevis relaterade till beräknbarhet.

Eftersom varje fysiskt objekt eller egenskap i princip kan beskrivas till nästan utmattning av en sträng bitar, kan objekt och egenskaper också sägas ha algoritmisk komplexitet. Faktum är att minska komplexiteten hos verkliga objekt till program som producerar objekten som utgång, är ett sätt att se vetenskapens företag. De komplexa föremålen runt oss tenderar att komma från tre huvudsakliga genereringsprocesser; uppkomst , evolution och intelligens , med de objekt som produceras av varje som tenderar mot större algoritmisk komplexitet.

Beräkningskomplexitet är en uppfattning som ofta används i teoretisk datavetenskap för att bestämma den relativa svårigheten att beräkna lösningarna för 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 rör naturen hos två av dessa komplexitetsklasser. Komplexitetsklasser inkluderar problem som är mycket svårare än något man kan möta i matematik fram till kalkylen. Det finns många tänkbara problem i beräkningskomplexitetsteorin som skulle kräva en 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 gav viktiga bidrag i slutet av 60-talet med algoritmisk informationsteori. Principen om lägsta meddelandelängd, nära besläktad med algoritmisk komplexitet, ger mycket av grunden för statistisk och induktiv inferens och maskininlärning.