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 af programmer altid være den 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 veluddannet gæt. Dette resultat (en strengs beregningskompleksitet) viser sig at være meget vigtigt for bevis relateret til beregbarhed.
Da ethvert fysisk objekt eller egenskab i princippet kan beskrives til næsten udmattelse af en streng bits, kan objekter og egenskaber også siges at have algoritmisk kompleksitet. Faktisk er reduktion af kompleksiteten af objekter i den virkelige verden til programmer, der producerer objekterne som output, en måde at se videnskabens virksomhed på. De komplekse objekter omkring os har en tendens til at komme fra tre hovedgenererende processer; fremkomst , evolution og intelligens , med de objekter, der produceres af hver, tendens mod større algoritmisk kompleksitet.
Beregningskompleksitet er en opfattelse, der ofte bruges i teoretisk datalogi til at bestemme den relative vanskelighed ved at beregne løsningerne til brede klasser af matematiske og logiske problemer. Mere end 400 kompleksitetsklasser findes, og yderligere klasser opdages kontinuerligt. Det berømte P = NP- spørgsmål vedrører arten af to af disse kompleksitetsklasser. Kompleksitetsklasser inkluderer problemer langt vanskeligere end noget man måtte konfrontere i matematik op til calculus. Der er mange tænkelige problemer i beregningskompleksitetsteorien, som ville kræve en næsten uendelig lang tid 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 minimum beskedlængde, tæt forbundet med algoritmisk kompleksitet, giver meget af grundlaget for statistisk og induktiv inferens og maskinlæring.