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 udtalding med en række bits, genstande og egenskaber kan være SHjælp til 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 intelligens , med de genstande, der er produceret af hver, der har en tendens til større algoritmisk kompleksitet.
Beregningskompleksitet er en forestilling, der ofte bruges i teoretisk datalogi til at bestemme den relative vanskelighed ved at beregne løsningen til brede klasser af 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 nogetkan konfrontere i matematik op til beregning. Der er mange tænkelige problemer i beregningskompleksitetsteori, der kræver 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.