Wat is algoritmische complexiteit?
Algorithmische complexiteit (computationele complexiteit of Kolmogorov-complexiteit) is een fundamenteel idee in zowel computationele complexiteitstheorie als algoritmische informatietheorie en speelt een belangrijke rol bij formele inductie.
De algoritmische complexiteit van een binaire string wordt gedefinieerd als het kortste en meest efficiënte programma dat de string kan produceren. Hoewel er een oneindig aantal programma's is dat elke gegeven string kan produceren, zal één programma of groep programma's altijd het kortste zijn. Er is geen algoritmische manier om het kortste algoritme te vinden dat een gegeven string uitvoert; dit is een van de eerste resultaten van de computationele complexiteitstheorie. Toch kunnen we een weloverwogen gok doen. Dit resultaat (de rekencomplexiteit van een string) blijkt erg belangrijk te zijn voor bewijzen met betrekking tot de berekenbaarheid.
Aangezien elk fysiek object of eigenschap in principe kan worden beschreven als bijna uitgeput door een reeks bits, kunnen objecten en eigenschappen ook algoritmische complexiteit hebben. In feite is het verminderen van de complexiteit van objecten uit de praktijk tot programma's die de objecten als output produceren, een manier om de onderneming van wetenschap te bekijken. De complexe objecten om ons heen zijn meestal afkomstig van drie hoofdgeneratieprocessen; opkomst , evolutie en intelligentie , waarbij de door elk geproduceerde objecten neigen naar een grotere algoritmische complexiteit.
Computationele complexiteit is een begrip dat vaak in de theoretische informatica wordt gebruikt om de relatieve moeilijkheid te bepalen van het berekenen van de oplossingen voor brede klassen van wiskundige en logische problemen. Er zijn meer dan 400 complexiteitsklassen en er worden voortdurend aanvullende klassen ontdekt. De beroemde P = NP- vraag betreft de aard van twee van deze complexiteitsklassen. Complexiteitsklassen bevatten problemen die veel moeilijker zijn dan alles wat men tot wiskunde in de wiskunde zou kunnen tegenkomen. Er zijn veel denkbare problemen in de computationele complexiteitstheorie die een bijna oneindige hoeveelheid tijd vereisen om op te lossen.
Algoritmische complexiteit en gerelateerde concepten werden in de jaren 1960 ontwikkeld door tientallen onderzoekers. Andrey Kolmogorov, Ray Solomonoff en Gregory Chaitin hebben in de late jaren 60 belangrijke bijdragen geleverd met algoritmische informatietheorie. Het principe van minimale berichtlengte, nauw verwant met algoritmische complexiteit, biedt veel van de basis voor statistische en inductieve inferentie en machine learning.