Hva er algoritmisk kompleksitet?

Algoritmisk kompleksitet, (beregningskompleksitet, eller Kolmogorov -kompleksitet), er en grunnleggende idé i både Computational Complexity Theory 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 gruppe av programmer alltid være det korteste.Det er ingen algoritmisk måte å finne den korteste algoritmen som sender ut en gitt streng;Dette er et av de første resultatene av beregningskompleksitetsteori.Likevel kan vi gjøre en utdannet gjetning.Dette resultatet, (beregningskompleksiteten til en streng), viser seg å være veldig viktig for bevis relatert til beregningsbarhet.

Siden ethvert fysisk objekt eller egenskap i prinsippet kan beskrives til nær-uttømming av en streng med biter, objekter og egenskaperKan sies å ha algoritmisk kompleksitet også.Å redusere kompleksiteten i virkelige objekter i den virkelige verden til programmer som produserer objektene som output, er faktisk en måte å se vitenskapens virksomhet.De komplekse objektene rundt oss har en tendens til å komme fra tre hovedgenerasjonsprosesser; Fremvekst , Evolusjon og intelligens , med objektene produsert av hver og en som har en tendens til større algoritmisk kompleksitet.

Beregningskompleksitet er en forestilling som ofte brukes i teoretisk informatikk for å bestemme den relative vanskeligheten med å beregne løsningene til brede klasserav matematiske og logiske problemer.Mer enn 400 kompleksitetsklasser eksisterer, og flere klasser blir kontinuerlig oppdaget.Den berømte P ' NP Spørsmål angår arten av to av disse kompleksitetsklassene.Kompleksitetsklasser inkluderer problemer som er langt vanskeligere enn noe man kan konfrontere i matematikk opp til kalkulus.Det er mange tenkelige problemer i beregningskompleksitetsteori som vil kreve en nesten uendelig 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.