Complexitatea Kolmogorov

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 14 aprilie 2022; verificările necesită 2 modificări .

În teoria informației algoritmice, complexitatea Kolmogorov a unui obiect (cum ar fi un text) este o măsură a resurselor de calcul necesare pentru a defini cu exactitate acel obiect.

Complexitatea Kolmogorov este cunoscută și sub denumirea de complexitate descriptivă, complexitate Kolmogorov –Khaitin , complexitate stocastică , entropie algoritmică sau complexitate algoritmică .

Exprimă posibilitatea unei descrieri fractale.

De exemplu, luați în considerare două șiruri de caractere lungi de 64 de caractere și care conțin doar litere mici și numere:

abababababababababababababababababababababababababababababababab 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfdppa0q7nieieqe9noc4cvafzf

Prima linie are o descriere simplă în limbaj natural, și anume de 32 de ori , formată din 10 caractere. A doua linie nu are o descriere simplă evidentă folosind același set de caractere, în afară de linia în sine, care are 64 de caractere.

Mai formal, complexitatea unui șir este lungimea descrierii acelui șir într-un limbaj de descriere universal . Capacitatea complexității de a se schimba în ceea ce privește alegerea limbajului de descriere este discutată mai jos. Se poate demonstra că complexitatea Kolmogorov a oricărui șir nu poate fi cu mai mult de câțiva octeți mai mult decât lungimea șirului în sine. Șirurile a căror complexitate Kolmogorov depinde slab de dimensiunea șirului în sine nu sunt considerate complexe.

Definiție

Pentru a defini complexitatea Kolmogorov, trebuie mai întâi să definim limbajul de descriere a șirurilor. Un astfel de limbaj de descriere se poate baza pe orice limbaj de programare, cum ar fi Lisp , Pascal sau Java . Dacă este un program a cărui ieșire este șirul , atunci este o descriere a . Lungimea descrierii este lungimea ca șir. În cursul determinării lungimii , lungimile subprogramelor utilizate în . Lungimea oricărei constante întregi care apare în este numărul de biți necesari pentru a reprezenta , care este (aproximativ) . $P$ $X$ $P$ $X$ $P$ $P$ $P$ $n$ $P$ $n$ $\log _{2}n$

Putem alege alternativ o codificare pentru mașina Turing , unde codificarea este o funcție care mapează fiecare mașină Turing la un șir de biți . Dacă este o mașină Turing care dă un șir ca intrare , atunci șirul combinat este o descriere pentru . Aceasta este o abordare teoretică care este mai potrivită pentru construirea de dovezi formale detaliate și este preferată în literatura de cercetare. Calculul lambda binar poate oferi cea mai simplă definiție a complexității. În acest articol, adoptăm o abordare informală. $M$ $\langle M\rangle$ $M$ $w$ $X$ $\langle M\rangle w$ $X$

Orice linie are cel puțin o descriere, adică un program $s$

funcția GenerateFixedString() returnează s

Dacă descrierea , este de lungime minimă, adică folosește cel mai mic număr de caractere, atunci se numește descriere minimă , iar lungimea , adică numărul de caractere din această descriere, este complexitatea Kolmogorov , . Simbolic: $s$ $d(e)$ $s$ $d(e)$ $s$ $K(e)$

K(s)=|d(s)|.

Să luăm în considerare modul în care alegerea limbajului descrierii afectează valoarea lui și să arătăm că efectul schimbării limbajului descrierii este limitat. $K$

Teorema . Dacă și sunt funcții de complexitate legate de limbajele de descriere și , atunci există o constantă (în funcție doar de limbi și ) astfel încât $K_1$ $K_{2}$ $L_{1}$ $L_{2}$ $c$ $L_{1}$ $L_{2}$

\forall s|K_{1}(s)-K_{2}(s)|\leqslant c.

Dovada . În schimb, este suficient să demonstrăm că există o constantă astfel încât pentru toate șirurile de biți $c$ $s$

K_{1}(s)\leqslant K_{2}(s)+c.

Să presupunem că există un program în limbaj care acționează ca un interpret pentru : $L_{1}$ $L_{2}$

funcția InterpretLanguage( șir p )

unde este programul lingvistic . Interpretul se caracterizează prin următoarea proprietate: $p$ $L_{2}$

Valoarea returnată ca rezultat al lucrului InterpretLanguageasupra datelor de intrare va fi rezultatul lucrării .

p

p

Astfel, dacă este un program într-o limbă care este descrierea minimă a , atunci ( ) returnează un șir . Lungimea acestei descrieri este suma: $P$ $L_{2}$ $s$ InterpretLanguage $P$ $s$ $s$

Lungimea programului InterpretLanguage, care poate fi luată ca o constantă . $c$
Lungimea definită de . $P$ $K_{2}(e)$

Aceasta dovedește limita superioară necesară.

Istorie și context

Teoria algoritmică a informației este un domeniu al informaticii care studiază complexitatea lui Kolmogorov și alte măsuri complexe pentru șiruri (sau alte structuri de date ).

Ideea teoriei complexității Kolmogorov se bazează pe o teoremă cheie descoperită pentru prima dată de Ray Solomonoff , care a publicat-o în 1960, descriind-o în A Preliminary Report on a General Theory of Inductive Inference [1] ca parte a invenției sale a probabilității algoritmice. . El a oferit o descriere mai completă în publicațiile sale „A Formal Theory of Inductive Inference” , părțile 1 și 2 din revista Information and Control [2] [3] , realizată în 1964.

Mai târziu , A. N. Kolmogorov a publicat independent această teoremă în revista Information Transmission Problems [4] , Gregory Khaitin a prezentat și această teoremă în revista J. ACM" . Lucrarea lui Khaitin a fost trimisă în octombrie 1966, revizuită în decembrie 1968 și citează atât lucrările lui Solomonoff, cât și ale lui Kolmogorov. [5]

Teorema afirmă că printre algoritmii care restabilesc (decodifică) șiruri din descrierile (codurile) lor, există unul optim. Acest algoritm pentru toate șirurile oferă aceleași coduri scurte ca și cele furnizate de alți algoritmi, cu diferența printr-o constantă în funcție de algoritm, dar nu și de șirul în sine. Solomonoff a folosit acest algoritm și lungimile de cod pe care le-a furnizat pentru a determina „probabilitatea universală” a șirurilor, pe care s-ar putea baza deducerea inductivă a caracterelor ulterioare dintr-un șir. Kolmogorov a folosit această teoremă pentru a defini mai multe funcții de șir: complexitate, aleatorie și informație.

Când Kolmogorov a aflat despre opera lui Solomonoff, el și-a recunoscut prioritatea [6] . Timp de câțiva ani, opera lui Solomonoff a fost mai cunoscută în URSS decât în Occident. Cu toate acestea, este obișnuit în comunitatea științifică să se asocieze acest tip de complexitate cu Kolmogorov, care a vorbit despre caracterul aleatoriu al secvențelor, în timp ce probabilitatea algoritmică a devenit asociată cu Solomonoff, care s-a concentrat pe predicție folosind descoperirea sa a distribuției de probabilitate anterioară universală.

Există și alte variante ale complexității Kolmogorov sau ale informațiilor algoritmice. Unul dintre cele mai utilizate pe scară largă se bazează pe programe autolimitante și este asociat în principal cu L. A. Levin (1974). O abordare axiomatică a complexității lui Kolmogorov bazată pe axiomele lui Bloom (1967) a fost introdusă de M. Burgin (1982).

Unii oameni cred că numele „complexitatea Kolmogorov” este un exemplu al efectului Matei [7] .

Principalele consecințe

În raționamentul următor, ne referim la complexitatea șirului . $K(e)$ $s$

Este ușor de observat că descrierea minimă a unui șir nu poate fi mai mare decât șirul în sine: programul de mai sus GenerateFixedString, a cărui ieșire este mai mare cu o sumă fixă. $s$ $s$

Teorema . Există o constantă astfel încât $c$

\forall s\,K(s)\leqslant |s|+c.

Incomputabilitatea complexității Kolmogorov

Prima consecință este că nu există o modalitate eficientă de calcul . $K$

Teorema . este o funcție necalculabilă . $K$

Cu alte cuvinte, problema calculării complexității algoritmice a unui șir arbitrar este de nerezolvată din punct de vedere algoritmic - nu există niciun program care să ia ca intrare și ieșire un număr întreg . Să arătăm acest lucru cu o contradicție prin crearea unui program care creează un șir care poate fi creat doar de un program mai lung. Să presupunem că există un program $s$ $s$ $K(e)$

funcția KolmogorovComplexitate( șir s )

care ia ca intrare si returneaza . Acum luați în considerare programul $s$ $K(e)$

funcția GenerateComplexString( int n ) pentru i = 1 la infinit: pentru fiecare șir s de lungime exact i dacă KolmogorovComplexity( s ) >= n return s ieși

Acest program apelează o subrutină KolmogorovComplexity. Programul încearcă fiecare linie, începând cu cea mai scurtă, până când găsește o linie cu complexitate cel puțin , pe care o returnează. Prin urmare, având în vedere orice număr întreg pozitiv , acesta produce un șir cu complexitatea Kolmogorov cel puțin . Acest program are propria lungime fixă . Intrarea programului este un număr întreg , iar dimensiunea este măsurată prin numărul de biți necesari pentru a-l reprezenta, care este . În continuare, luați în considerare următorul program: $n$ $n$ $n$ $U$ GenerateComplexString $n$ $n$ $\log _{2}n$

funcția GenerateParadoxicalString() returnează GenerateComplexString(n 0 )

Acest program apelează GenerateComplexStringca o subrutină și are, de asemenea, un parametru liber . Acest program scoate un șir a cărui complexitate este de cel puțin . Cu o alegere favorabilă a parametrului, ajungem la o contradicție. Pentru a alege această valoare, rețineți că este descrisă de un program a cărui lungime nu este mai mare decât $n_{0}$ $s$ $n_{0}$ $n_{0}$ $s$ GenerateParadoxicalString

U+\log _{2}n_{0}+C,

unde constanta este adăugată din cauza programului . Deoarece crește mai repede decât , există o valoare astfel încât $C$ GenerateParadoxicalString $n$ $\log _{2}n$ $n_{0}$

U+\log _{2}n_{0}+C<n_{0}.

Dar acest lucru contrazice definiția că există o complexitate de cel puțin . Adică, prin definiție ( ), este permis ca șirul returnat de programul GenerateParadoxicalString să poată fi creat de programul cu o lungime sau mai mare, dar mai scurtă decât . Deci programul nu poate calcula de fapt complexitatea unui șir aleator. $n_{0}$ $s$ $s$ $n_{0}$ GenerateParadoxicalString $n_{0}$ KolmogorovComplexity

Aceasta este o dovadă prin contradicție, în care contradicția este similară cu paradoxul lui Berry : „Să fie cel mai mic număr întreg pozitiv care nu poate fi numit cu mai puțin de douăzeci de cuvinte englezești”. [8] De asemenea, este posibil să se arate non-computabilitatea prin reducerea non-computabilității la o problemă de oprire , deoarece și sunt echivalente cu Turing. [9] $n$ $K$ $H$ $K$ $H$

Există un corolar în comunitatea de programare cunoscut sub numele de teorema de utilizare completă , care afirmă că nu există un compilator care să fie perfect optimizat pentru dimensiune.

Regula lanțului pentru complexitatea Kolmogorov

Regula lanțului pentru complexitatea Kolmogorov prevede că

K(X,Y)=K(X)+K(Y\mid X)+O{\big (}\log K(X,Y){\big )}.

Afirmă că cel mai scurt program care reproduce și este cel mult mai mare decât programul care reproduce și programul care reproduce dat . Folosind această expresie, se poate defini un analog al informațiilor reciproce pentru complexitatea Kolmogorov. $X$ $Y$ $\log K(X,Y)$ $X$ $Y$ $X$

Compresie

Calcularea limitei superioare pentru este ușoară: trebuie doar să comprimați șirul folosind o metodă, să implementați decompresorul corespunzător în limba aleasă, să conectați decompresorul la șirul comprimat și să măsurați lungimea șirului rezultat. $K(e)$ $s$

Șirul este comprimat de dacă are o descriere a cărei lungime nu depășește . Aceasta este echivalentă cu o declarație . Dacă acest lucru nu se face, atunci nu este comprimat de . Un șir care nu este compresibil cu 1 se numește pur și simplu incompresibil; prin principiul lui Dirichlet , trebuie să existe șiruri incompresibile , deoarece există șiruri de biți de lungime , dar numai șiruri de lungime mai mică decât [10] . $s$ $c$ $|s|-c$ $K(s)\leqslant |s|-c$ $s$ $c$ $2^{n}$ $n$ $2^{n}-1$ $n$

Din același motiv, majoritatea șirurilor sunt complexe în sensul că nu pot fi comprimate semnificativ: nu cu mult mai puțin decât lungimea în biți. Pentru a clarifica, să reparăm valoarea lui . Există șiruri de biți de lungime . Distribuția uniformă de probabilitate pe spațiul acestor șiruri de biți este determinată de exact egal cu factorul de ponderare pentru fiecare șir de lungime . $K(e)$ $|s|$ $s$ $n$ $2^{n}$ $n$ $2^{{-n}}$ $n$

Teorema . Probabilitatea ca un șir să nu fie comprimat este cel puțin egală cu o distribuție uniformă a probabilității pe spațiul șirurilor de biți de lungime . $c$ $1-2^{-c+1}+2^{-n)$ $n$

Pentru a demonstra această teoremă, observăm că numărul descrierilor lungimii nu depășește , obținut dintr-o progresie geometrică : $n.c.$

1+2+2^{2}+\ldots +2^{nc}=2^{n-c+1}-1.

Rămâne cel puțin

2^{n}-2^{n-c+1}+1

șiruri de biți care sunt incompresibile pe . Împărțiți la pentru a determina probabilitatea . $c$ $2^{n}$

Teorema de incompletitudine a lui Khaitin

Știm că în setul tuturor șirurilor posibile, majoritatea șirurilor sunt complexe în sensul că nu pot fi descrise într-un mod suficient de concis. Cu toate acestea, se dovedește că faptul că un anumit șir este complex nu poate fi dovedit formal dacă complexitatea șirului este peste un anumit prag. Formalizarea exactă este prezentată mai jos. Pentru început, fixăm un anumit sistem axiomatic pentru numerele naturale . Sistemul axiomatic trebuie să fie suficient de puternic pentru ca o judecată precisă asupra complexității unui șir să poată fi mapată la o formulă din sistemul axiomatic . Această corespondență trebuie să aibă următoarea proprietate: dacă este derivată din axiome , atunci propoziția corespunzătoare este adevărată. ${\mathbf {s}}$ $\mathbf {A}$ ${\mathbf {F}}_{{\mathbf {A}}}$ $s$ ${\mathbf {F}}_{{\mathbf {A}}}$ ${\mathbf {s}}$ $\mathbf {A}$

Teorema . Există o astfel de constantă (care depinde numai de un anumit sistem axiomatic și de limbajul de descriere ales) încât pentru orice rând enunțul $L$

K(s)\geqslant L

nu poate fi dovedit în . ${\mathbf {s}}$

Totuși, așa cum este ușor de înțeles, afirmația va fi adevărată pentru un număr infinit de rânduri, sau mai degrabă, pentru toate rândurile, cu excepția unui număr finit. $K(s)\geqslant L$

Demonstrarea teoremei se bazează pe construcția autoreferențială utilizată în paradoxul lui Berry . Dovada prin contradictie. Dacă teorema nu este adevărată, atunci

Ipoteza (X) : Pentru orice număr întreg există un șir pentru care există o derivare a formulei „ ” (pentru care am presupus că poate fi formalizat în ).

n

s

{\mathbf {s}}

K(s)\geqslant n

{\mathbf {s}}

Luați în considerare un program care implementează o enumerare eficientă a tuturor dovezilor formale în ${\mathbf {s}}$

funcția NthProof( int n )

care ia n ca intrare și produce o dovadă. Unele dintre ele dovedesc o formulă ca „ ”, unde s și n sunt constante în limbaj . Există un program care verifică dacă a n- a dovadă demonstrează formula " ": $K(s)\geqslant n$ ${\mathbf {s}}$ $K(s)\geqslant L$

funcția NthProofProvesComplexityFormula( int n )

În schimb, șirul s și numărul L pot fi calculate de programe

funcția StringNthProof( int n ) funcția ComplexityLowerBoundNthProof( int n )

Luați în considerare acum următorul program:

funcția GenerateProvablyComplexString( int n ) pentru i = 1 la infinit: dacă NthProofProvesComplexityFormula(i) și ComplexityLowerBoundNthProof(i) ≥ n returnează StringNthProof( i )

Dat n ca intrare , acest program verifică fiecare demonstrație până când găsește un șir s și o demonstrație cu formula K ( s ) ≥ L pentru unele L ≥ n . Acest program se oprește pe Guess (X) . Fie ca acest program să aibă lungimea U . Există un număr n 0 astfel încât U + log 2 n 0 + C < n 0 , unde C este lungimea suplimentară a programului

funcția GenerateProvablyParadoxicalString() returnează GenerateProvablyComplexString( n 0 )

Rețineți că numărul n 0 este, de asemenea, codificat în acest program, necesitând informații de jurnal 2 ( n 0 ). Programul GenerateProvablyParadoxicalString produce un șir s pentru care există un L astfel încât K ( s ) ≥ L poate fi dedus la , unde L ≥ n 0 . În special, K ( s ) ≥ n 0 este adevărat pentru acesta . Totuși, s poate fi descris printr-un program de lungime U + log 2 n 0 + C , deci complexitatea sa este mai mică decât n 0 . Contradicția rezultată dovedește falsitatea Ipotezei (X) . ${\mathbf {s}}$

Idei similare sunt folosite pentru a demonstra proprietățile constantei lui Chaitin .

Lungimea minimă a mesajului

Principiul lungimii minime a mesajului în inferența statistică și inductivă și în învățarea automată a fost dezvoltat de Wallace ( în engleză CS Wallace ) și Bolton ( în engleză DM Boulton ) în 1968. Principiul MDS este bayesian (include probabilități anterioare) și teoretic informațional. Are proprietățile dezirabile de invarianță statistică (transformări de inferență cu reparametrizare), conectivitate statistică (chiar și pentru o problemă foarte dificilă, principiul va converge către modelul de bază) și eficiență (un model bazat pe principiul MDS va converge către orice model valabil). modelul de bază cât mai repede posibil) . Wallace și Dowe ( ing. DL Dowe ) au arătat o relație formală între principiul MDS și teoria informației algoritmice (sau complexitatea Kolmogorov).

Șansa lui Kolmogorov

Conform definiției aleatoriei lui Kolmogorov (de asemenea aleatorii algoritmice), se spune că un șir este aleatoriu dacă și numai dacă este mai scurt decât orice program de calculator capabil să îl reproducă. Pentru a face această definiție precisă, un computer universal (sau o mașină Turing universală ) trebuie să fie fixat, astfel încât „program de calculator” să însemne programul pentru acea mașină universală. Aleatoriu în acest sens, șirul va fi „incompresibil”. Folosind principiul Dirichlet, este ușor de arătat că pentru orice mașină universală există șiruri aleatoare din punct de vedere algoritmic de orice lungime, dar proprietatea unui șir de a fi aleatoare din punct de vedere algoritmic depinde de alegerea mașinii universale.

Această definiție poate fi extinsă la secvențe infinite de caractere dintr-un alfabet finit. Definiția poate fi formulată în trei moduri echivalente. Prima modalitate folosește un analog eficient al teoriei măsurii; celălalt foloseşte o martingală eficientă . A treia modalitate de a o defini este aceasta: o secvență infinită este aleatorie dacă complexitatea Kolmogorov a segmentului său inițial crește suficient de repede - există o constantă c astfel încât complexitatea oricărui segment inițial de lungime n este de cel puțin n - c . Se pare că această definiție, spre deosebire de definiția aleatoriei șirurilor finite, nu depinde de alegerea mașinii universale.

Relația cu entropia

Conform teoremei Brudno, entropia unui sistem dinamic și complexitatea algoritmică a traiectoriilor din acesta sunt legate de relația pentru aproape toate . [unsprezece] $K(x;T)=h(T)$ $X$

Se poate arăta [12] că complexitatea Kolmogorov a rezultatului muncii unei surse de informație Markov este legată de entropia acesteia . Mai precis, complexitatea Kolmogorov a ieșirii unei surse de informații Markov, normalizată la lungimile ieșirii, converge aproape întotdeauna către entropia sursei.

Note

↑ Solomonoff, Ray Un raport preliminar asupra unei teorii generale a inferenței inductive // Raport V-131 : jurnal. - Cambridge, Ma.: Zator Co., 1960. - 4 februarie. revizuire Arhivatla 1 august 2020 laWayback Machine, noiembrie 1960.
↑ Solomonoff, Ray. O teorie formală a inferenței inductive Partea I // Informații și control : jurnal. - 1964. - Martie ( vol. 7 , nr. 1 ). - P. 1-22 . - doi : 10.1016/S0019-9958(64)90223-2 .
↑ Solomonoff, Ray. O teorie formală a inferenței inductive Partea II // Informații și control : jurnal. - 1964. - Iunie ( vol. 7 , nr. 2 ). - P. 224-254 . - doi : 10.1016/S0019-9958(64)90131-7 .
↑ Kolmogorov, A. N. Trei abordări ale definiției conceptului de „cantitate de informații” // Probleme de transmitere a informațiilor: jurnal. - 1965. - T. 1 , nr 1 . - S. 3-11 . (Rusă)
↑ Chaitin, Gregory J. On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers // Journal of the ACM : journal. - 1969. - Vol. 16 . - P. 407 . - doi : 10.1145/321526.321530 . Arhivat din original pe 25 august 2011.
↑ Kolmogorov, A. Baza logică pentru teoria informației și teoria probabilității (engleză) // IEEE Transactions on Information Theory : jurnal. - 1968. - Vol. 14 , nr. 5 . - P. 662-664 . - doi : 10.1109/TIT.1968.1054210 .
↑ Li, Ming; Paul Vitani. O introducere în complexitatea Kolmogorov și aplicațiile sale . — al 2-lea. - Springer, 1997. - ISBN 0387948686 .
↑ Original: „Să fie cel mai mic număr întreg pozitiv care nu poate fi definit în mai puțin de douăzeci de cuvinte în limba engleză”. $n$
↑ Peter Bro Miltersen. Note de curs pentru compresia datelor. 2. Complexitatea Kolmogorov (link inaccesibil) . Consultat la 17 februarie 2011. Arhivat din original pe 9 septembrie 2009. (nedefinit)
↑ Deoarece există șiruri de lungime , numărul de șiruri de lungime este , care este o progresie geometrică finită cu suma egală cu . $n_{L}=2^{L}$ $L$ $L=0,\ldots ,(n-1)$ ${\displaystyle n_{0}+n_{1}+\ldots +n_{n-1}=2^{0}+2^{1}+\ldots +2^{n-1))$ $2^{0}+2^{1}+\ldots +2^{n-1}=2^{0}\times (1-2^{n})/(1-2)=2 ^{n}-1$
↑ Copie arhivată . Preluat la 6 iunie 2013. Arhivat din original la 26 decembrie 2011. (nedefinit)
↑ http://arxiv.org/pdf/cs.CC/0404039

Literatură

Vereshchagin N.K. Cursul complexității Kolmogorov .
Vereshchagin N. K., Shen V. A. Kolmogorov complexitatea și aleatorietatea algoritmică . — MTsNMO, 2013.
Vyugin VV Kolmogorov complexitate și aleatoriu algoritmic .

Dicționare și enciclopedii	mare chinezesc Universalis