Vad är algoritmisk komplexitet?

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 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 varje given sträng, kommer ett program eller 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 av beräkningskomplexitetsteorin.Trots det kan vi göra en utbildad gissning.Detta resultat, (beräkningskomplexiteten för en sträng), visar sig vara mycket viktigt för bevis relaterade till beräkbarhet.

Eftersom något fysiskt objekt eller egenskap i princip kan beskrivas till nästan utflyttning av en sträng av bitar, objekt och egenskaperKan sägas ha algoritmisk komplexitet också.I själva verket är att minska komplexiteten i verkliga objekt till program som producerar objekten som output, ett sätt att se vetenskapsföretaget.De komplexa föremålen runt oss tenderar att komma från tre huvudgenererande processer; Framväxten , Evolution och Intelligens , med de objekt som produceras av varje tenderar mot större algoritmisk komplexitet.

Beräkningskomplexitet är en uppfattning som ofta används i teoretisk datavetenskap för att bestämma de relativa svårigheterna med att beräkna lösningarna till breda klasserav matematiska och logiska problem.Mer än 400 komplexitetsklasser finns och ytterligare klasser upptäcks kontinuerligt.Den berömda p ' np Frågan rör arten av två av dessa komplexitetsklasser.Komplexitetsklasser inkluderar problem som är mycket svårare än någonting man kan möta i matematik upp 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 minimimeddelandelängd, nära relaterad till algoritmisk komplexitet, ger mycket av grunden för statistisk och induktiv inferens och maskininlärning.