Hvad er algoritmisk kompleksitet?

Algoritmisk kompleksitet, (beregningskompleksitet eller Kolmogorov -kompleksitet), er en grundlæggende idé i både beregningskompleksitetsteori og algoritmisk informationsteori og spiller en vigtig rolle i formel induktion.

Den algoritmiske kompleksitet af en binær streng defineres som det korteste og mest effektive program, der kan producere strengen.Selvom der er et uendeligt antal programmer, der kan producere en given streng, vil et program eller en gruppe programmer altid være det korteste.Der er ingen algoritmisk måde at finde den korteste algoritme, der udsender en given streng;Dette er et af de første resultater af beregningskompleksitetsteorien.Alligevel kan vi komme med et uddannet gæt.Dette resultat (beregningskompleksiteten af en streng) viser sig at være meget vigtig for beviser relateret til beregningsevne.

Da ethvert fysisk objekt eller egenskab i princippet i princippet kan beskrives til næsten udtømmelser med en række bit, genstande og egenskaberkan siges at have algoritmisk kompleksitet også.Faktisk er det at reducere kompleksiteten af virkelige verdensobjekter til programmer, der producerer objekterne som output, en måde at se videnskabsvirksomheden på.De komplekse genstande omkring os har en tendens til at komme fra tre hovedgenererende processer; Fremkomst , Evolution og Intelligence , med de genstande, der er produceret af hver tendens til større algoritmisk kompleksitet.

Computational Complexity er en forestilling, der ofte bruges i teoretisk datalogi for at bestemme den relative vanskelighed ved at beregne løsningen til brede klasseraf matematiske og logiske problemer.Der findes mere end 400 kompleksitetsklasser, og der opdages yderligere klasser.Den berømte P ' NP -spørgsmål vedrører arten af to af disse kompleksitetsklasser.Kompleksitetsklasser inkluderer problemer, der er langt vanskeligere end noget, man kan konfrontere i matematik med beregning.Der er mange tænkelige problemer i beregningskompleksitetsteori, der ville kræve en næsten uendelig mængde tid til at løse.

Algoritmisk kompleksitet og relaterede koncepter blev udviklet i 1960'erne af snesevis af forskere.Andrey Kolmogorov, Ray Solomonoff og Gregory Chaitin gav vigtige bidrag i slutningen af 60'erne med algoritmisk informationsteori.Princippet om minimumsmeddelelseslængde, tæt knyttet til algoritmisk kompleksitet, giver meget af grundlaget for statistisk og induktiv inferens og maskinlæring.