Kolmogorovkomplexiteten av ett objekt, såsom en textsträng, är ett mått på beräkningsresurserna som krävs för att specificera objektet eller med andra ord ett mått på hur kaotiskt objektet är. Det tillhör områdetalgoritmisk informationsteori och är döpt efterAndrej Kolmogorov, som publicerade artiklar under 1960-talet om ämnet.^[1]

Vi betraktar följande två strängar:

101010101010101010101010101010101010101010

111000110100011111100001001010001001010000

Det är lätt att se vilken av dessa som är mer kaotisk. Den första strängen kan kort beskrivas som "10" skrivet 21 gånger. Den andra strängen blir däremot svårare att beskriva och har därmed högre Kolmogorovkomplexitet än den första. Som det formellt beskrivs nedan, mäter Kolmogorovkomplexiteten den minsta mängden resurser som behövs för att beskriva ett objekt. Men komplexiteten kan inte beräknas utan endast approximeras uppifrån.

Säg att vi har objektet τ, en beskrivning av denna kan då sägas vara något ω om,

${\displaystyle f(\omega )=\tau }$.

Den formella versionen av Kolmogorovkomplexitet är

där U är en UniversellTuringmaskin, d.v.s. en maskin som kan simulera en godtycklig maskin för godtycklig indata.

1. ${\displaystyle C(x)\le |x|+c}$, c är konstant.
2. ${\displaystyle C(xx)\le C(x)+c}$
3. För alla delvis beräknebara h är${\displaystyle C(h(x))\le C(x)+c_h}$, där c_h är längden av en beskrivning av h.
4. ${\displaystyle C(x|y)\le C(x)+c}$

Sats: För alla n finns det något x med |x| = n så att${\displaystyle C(x)\le n}$. Detta x kallar vi för kolmogorovslump.

Bevis: Antag motsatsen. Då är för alla x. Alltså måste det existera ett program p_x,${\displaystyle g(p_x)=x}$ och. Om${\displaystyle x\ne y}$ är ej heller${\displaystyle p_x\ne p_y}$. Men det finns${\displaystyle 2^n-1}$ program med kortare längd än n, och${\displaystyle 2^n}$ strängar av längden n. Om alla strängar av längd n har ett program som är kortare än n, måste det finnas ett program som producerar två strängar. Uppenbarligen är det omöjligt och därav måste det finnas minst en sträng av längd n som har ett program av minst längden n.

Kolmogorovkomplexitet kan tillämpas i ett stort antal områden, bland annat har det tillämpats i

• Per Martin-Löfs test för slumpmässighet, informationsteori för individuella objekt
• allmän sannolikhet, induktivt resonemang och interferens, förutsägbarhet
• kombinatorik, okompressibilitetsmetoden, grafteori
• logiskt djup, universell optimal sökning, beräkningstermodynamik, statistisk termodynamik och Boltzmann-entropi

Till exempel kan Kolmogorovkomplexitet tillämpas för att bevisa ett antal klassiska satser, som i följande exempel där teorin används för att bevisa att det finns oändligt många primtal.

Bevis för att det finns oändligt antal primtal: Antag först motsatsen, att det finns ett ändligt antal primtal. I så fall kan vi säga att det finns det k stycken primtal, p₁, p₂,...,p_k för k${\displaystyle \in \mathbb{N}}$. Vi kan då välja ett tal m${\displaystyle \in \mathbb{N}}$ och skriva det som en produkt av primtalen${\displaystyle m={p_1}^{e_1}\ast ...\ast {p_k}^{e_k}}$.

Låt m vara Kolmogorovslumpen av längden n. Vi kan påstå att det ger en kort beskrivning av m. Först för att${\displaystyle e_i\le \log m}$. Då är${\displaystyle |e_i|\le \log m}$. Vilket ger${\displaystyle |⟨e_1,...,e_k⟩|\le 2k\log \log m}$. Därav då${\displaystyle m\le 2^{n+1}}$ och${\displaystyle |⟨e_1,...,e_k⟩|\le 2k\log n+1}$ blir${\displaystyle C(m)=2k\log n+1+c}$. Då m är slumpmässigt valt blir${\displaystyle C(m)\ge n}$ falskt för stora n.

Kolmogorovkomplexitet gjordes känd av matematikernAndrej Kolmogorov, men definierades tidigare avRaymond J. Solomonoff som en del i hans arbete kring algoritmisk informationsteori^[2] ochmatematisk induktion och även senare avGregory J. Chaitin, som formulerade en rigorös definition i den artikel han publicerade 1969.^[3] Motivationen till Kolmogorovs arbete var informationsteoretisk och inriktad påslump/kaos medan Solomonoffs var motiverat av matematisk induktion.

I somliga fall kallas teorin för algoritmisk entropi. Detta härrör från attentropi i ett system är ett mått på systemets kaos. Inominformationsteori refererar entropi vanligast tillShannons entropi som delar flertalet egenskaper med Kolmogorovkomplexitet.

• http://people.cs.uchicago.edu/~fortnow/papers/kaikoura.pdf
• http://homepages.cwi.nl/~paulv/kolmogorov.html
• http://harnold.org/downloads/publications/kcim.pdf - Okompressibilitetsmetoden
• http://www.scholarpedia.org/article/Algorithmic_complexity
• http://www.cwi.nl/~paulv/papers/solomonoff.ps

• Informationsteori
• Komplexitetsteori

• Wikipedia:Projekt översätta källmallar