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 nesten-uttrekking av en streng med biter, objekter og egenskaper kan være sHjelp til å 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 som pleier 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 brede klasser av matematiske og logiske problemer. Mer enn 400 kompleksitetsklasser eksisterer, og flere klasser blir kontinuerlig oppdaget. Det berømte p = np spørsmålet angår arten av to av disse kompleksitetsklassene. Kompleksitetsklasser inkluderer problemer langt vanskeligere enn noe annetKan 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.