Hva er algoritmisk kompleksitet?

Algoritmisk kompleksitet (beregningskompleksitet, eller Kolmogorov-kompleksitet), er en grunnleggende ide i både beregningskompleksitetsteori og algoritmisk informasjonsteori , og spiller en viktig rolle i formell induksjon.

Den algoritmiske kompleksiteten til en binær streng er definert som det korteste og mest effektive programmet som kan produsere strengen. Selv om det er et uendelig antall programmer som kan produsere en gitt streng, vil ett program eller en gruppe programmer alltid være den korteste. Det er ingen algoritmisk måte å finne den korteste algoritmen som gir ut en gitt streng; dette er et av de første resultatene fra beregningsmessig kompleksitetsteori. Likevel kan vi komme med en utdannet gjetning. Dette resultatet (beregningskompleksiteten til en streng) viser seg å være veldig viktig for bevis relatert til beregbarhet.

Siden ethvert fysisk objekt eller eiendom i prinsippet kan beskrives til nesten utmattelse av en streng med biter, kan objekter og egenskaper sies å ha algoritmisk kompleksitet også. Å redusere kompleksiteten til objekter i den virkelige verden til programmer som produserer objektene som output, er faktisk en måte å se vitenskapens virksomhet på. De komplekse objektene rundt oss har en tendens til å komme fra tre hovedgenerasjonsprosesser; fremvekst , evolusjon og intelligens , med gjenstandene produsert av hver tendens mot større algoritmisk kompleksitet.

Beregningskompleksitet er en forestilling som ofte brukes i teoretisk informatikk for å bestemme den relative vanskeligheten med å beregne løsningene til store klasser av matematiske og logiske problemer. Mer enn 400 kompleksitetsklasser eksisterer, og ytterligere klasser oppdages kontinuerlig. Det berømte P = NP- spørsmålet angår arten av to av disse kompleksitetsklassene. Kompleksitetsklasser inkluderer problemer som er langt vanskeligere enn noe man måtte konfrontere i matematikk fram til kalkulus. Det er mange tenkelige problemer i beregningskompleksitetsteorien som vil kreve en nesten uendelig lang tid å løse.

Algoritmisk kompleksitet og relaterte konsepter ble utviklet på 1960-tallet av dusinvis av forskere. Andrey Kolmogorov, Ray Solomonoff og Gregory Chaitin ga viktige bidrag på slutten av 60-tallet med algoritmisk informasjonsteori. Prinsippet om minimum meldingslengde, nært knyttet til algoritmisk kompleksitet, gir mye av grunnlaget for statistisk og induktiv inferens og maskinlæring.