Complexitat de Kolmogórov

En la teoria de la computació, la complexitat de Kolmogórov és una mesura de la quantitat de recursos computacionals necessaris per a poder descriure una certa quantitat d'informació. El nom es deu a Andrei Kolgomórov. La complexitat de Kolmogórov també es denomina complexitat descriptiva o complexitat de Kolmogórov-Chaitin, complexitat estocàstica, o entropia algorítmica.^[1]

Per poder definir la complexitat de Kolmogórov, primer s'ha d'especificar un llenguatge descriptiu per a les seqüències o cadenes. Aquest llenguatge pot basar-se en qualsevol llenguatge de programació com ara Lisp o Pascal. Si P és un programa que genera com sortides seqüències de tipus x, llavors P és una descripció del conjunt de x. La longitud de la descripció és la longitud de P com a seqüència de caràcters. Per determinar la longitud de P, ha d'adonar-se de les longituds de totes les subrutines emprades en P. La longitud de qualsevol nombre enter n que aparegui en el programa P és la quantitat de bits requerits per representar n, això és, log₂n.^[2]

Definició

Podem intentar comprendre la complexitat de Kolmogórov amb aquest exemple. Considerem dues cadenes de caràcters de 32 lletres minúscules i dígits:

abababababababababababababababab

4c1j5b2p0cv4w1x8rx2y39umgw5q85s7

La primera cadena la podem definir fàcilment com a “Escriure ab 16 cops”, una “ordre” que consta de 19 caràcters en català. Per l'altra banda, la segona cadena no té una forma clara de ser definida exceptuant “Escriu 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7”, que té una longitud de 39 caràcters en català. Llavors, en aquest exemple concret, podem determinar que l'operació d'especificar la primera ordre té menys complexitat que la segona.

Més formalment, la complexitat d'una cadena de caràcters és la longitud de la descripció més curta d'aquesta en un llenguatge de descripció fix (La sensibilitat de l'elecció d'un llenguatge respecte de la complexitat es discuteix més avall). Es pot demostrar que la Complexitat de Kolmogórov d'una cadena de caràcters no pot ser major a uns bytes més que la longitud de la cadena mateixa. Una cadena com la primera de l'exemple anterior, que té una complexitat petita amb comparació a la cadena original no es considera complexa.

La complexitat de Kolmogórov pot ser definida per qualsevol objecte matemàtic, però per simplicitat només utilitzarem cadenes de caràcters. Primer hem d'especificar un llenguatge per a la descripció de les cadenes de caràcters, el llenguatge pot ser basat en qualsevol llenguatge de programació, com Lisp, Pascal o Java. Si P és un programa que produeix una cadena x, llavors P és una descripció de x. La llargada de la descripció només és la llargària de P multiplicat pel nombre de bits que ocupa cada caràcter de P.

Tota cadena de caràcters té com a mínim una manera de descriure-la. Per la segona cadena del nostre exemple tenim el programa:

funció GenerarCadena2()
retornar “4c1j5b2p0cv4w1x8rx2y39umgw5q85s7”

Mentre que per la primera cadena ho podem escriure amb pseudocodi com a:

funció GenerarCadena1()
retornar “ab” × 16

Si la descripció d(s) d'una cadena s és la més curta possible, s'anomena la descripció mínima d's, i la longitud de d(s) és la seva complexitat de Kolmogórov, que s'escriu com K(s). Simbòlicament, això s'expressaria com:

$K(s)=|d(s)|$

Encara que la longitud de la descripció més curta es pugui veure afectada per l'elecció de llenguatge de descripció, aquest efecte està fitat (com a resultat del teorema de la invariància).

Teorema de la Invariància

Tractament Informal

Hi ha alguns llenguatges de descripció òptims en el sentit que donada qualsevol descripció d'un objecte en un llenguatge de descripció qualsevol, aquesta descripció es pot fer servir a un llenguatge òptim amb una sobrecàrrega constant. La constant només depèn dels llenguatges involucrats, i no de l'objecte en si o la seva descripció.

Posem un exemple d'un llenguatge de descripció òptim:

La primera part defineix un altre llenguatge de descripció.

La segona part és la descripció de l'objecte en aquest llenguatge.

En termes més tècnics, la primera part és una descripció d'un programa, i la segona part és l'entrada per al programa per produir l'objecte com a sortida.

Llavors, el teorema de la invariància diu: Donat qualsevol llenguatge de descripció L, el llenguatge de descripció òptim és com a mínim igual d'eficient que L, amb una sobrecàrrega constant.

Demostració: Qualsevol descripció D en L es pot convertir en una descripció en el llenguatge òptim per, primer descriure L com un programa P (primera part), i després utilitzar la descripció D com a entrada del programa P (segona part). La longitud total d'aquesta nova descripció D' és aproximadament:

$|D'|=|P|+|D|$

On la longitud de P és constant i, per tant, no depèn de D. Llavors, com a màxim hi ha un increment constant sense importar l'objecte que s'està descrivint. En conseqüència, el llenguatge òptim és universal fins a aquesta constant.

Tractament Formal

Teorema: Si K₁ i K₂ són funcions de complexitat relatives a llenguatges de descripció Turing complets L₁ i L₂, llavors hi ha una constant c, que depèn només dels llenguatges L₁ i L₂ agafats, tal que:

$\forall s.-c\leq K_{1}(s)-K_{2}(s)\leq c$ .

Demostració: Per simetria, és suficient provar que hi ha una constant c que per a totes les cadenes s.

$K_{1}(s)\leq K_{2}(s)+c$

Ara, suposem que hi ha un programa en el llenguatge L₁ que actua com un intèrpret de L₂:

funció InterpretarLlenguatge(cadena p)

on p és un programa a L₂. L'intèrpret es caracteritza per la següent propietat:

Córrer InterpretarLlenguatge en l'entrada p retorna el resultat d'executar p.

Per tant, si P és un programa a L₂ que és descripció mínima de s, llavors InterpretarLlenguatge(P) retorna s. La longitud d'aquesta descripció és la suma de

La longitud del programa InterpretarLlenguatge, que podem considerar la constant c.
La longitud de P que, per definició, és K₂(s).

Això demostra la fita superior que buscàvem.

Història i context

La teoria algorísmica de la informació és l'àrea de la ciència de la computació que estudia la complexitat de Kolmogórov i altres mètriques de complexitat en strings (entre altres estructures de dades).

El concepte i la teoria darrera de la complexitat de Kolmogórov es basa en un teorema enunciat pel Ray Solomonoff, publicat l'any 1960, en l'article "A Preliminary Report on a General Theory of Inductive Inference" com a part de la seva invenció de la probabilitat algorítmica. Va acabar de donar-ne una descripció més completa en articles posteriors, amb "A Formal Theory of Inductive Inference", parts 1 i 2, dins la revista Information and Control, edicions de març i juny de 1964 respectivament.

Posteriorment, Andrei Kolgomórov va publicar independentment el mateix teorema a "Problems Inform. Transmission", l'any 1964. Gregory Chaitin presenta el teorema a "J.ACM" a un article entregat a octubre de 1966 i revisat a desembre de 1968, citant a Kolmogórov i Solomonoff.

El teorema diu que, entre els algoritmes que descodifiquen cadenes de les seves descripcions (codis), n'hi ha un d'òptim. Aquest algoritme, per a totes les cadenes, admet codis tan curts com els permet qualsevol altre algorisme fins a una constant que depèn dels algorismes, però no de les cadenes en si. Solomonoff va utilitzar aquest algorisme i les longituds de codi que permeten definir una "probabilitat universal" d'una cadena en què es pot basar la inferència inductiva dels dígits subsegüents de la cadena. Kolmogorov va usar aquest teorema per a definir diverses funcions de les cadenes, incloses la complexitat, l'aleatorietat i la informació.

Quan Kolmogórov es va adonar del treball de Solomonoff, va reconèixer la prioritat de Solomonoff. Durant diversos anys, l'obra de Solomonoff va ser més coneguda a la Unió Soviètica que al món occidental. El consens general de la comunitat científica, tanmateix, va ser associar aquest tipus de complexitat amb Kolmogórov, que es preocupava per l'aleatorietat d'una seqüència, mentre que la probabilitat algorítmica es va associar amb Solomonoff, que es va centrar en la predicció fent servir la seva invenció de la distribució de probabilitat prèvia universal. L'àrea més àmplia que inclou la complexitat descriptiva i la probabilitat s'anomena sovint complexitat de Kolmogórov. La informàtica Ming Li considera que això és un exemple de l'efecte Mateu: "... a qui més tingui, més se'n donarà..."

Hi ha diverses altres variants de la complexitat de Kolmogórov o la informació algorítmica. El més emprat es basa en programes autodelimitats, i es deu principalment a Leonid Levin (1974).

Un enfocament axiomàtic de la complexitat de Kolmogórov basat en els axiomes de Blum (Blum 1967) va ser introduït per Mark Burgin en el document presentat per a la seva publicació per Andrei Kolgomórov.

Resultats bàsics

A partir d'ara utilitzarem K(s) per denotar la complexitat de la cadena s.

No resulta massa difícil veure que la descripció mínima d'una cadena no pot ser més molt més llarga que aquesta. Com s'ha pogut veure abans el programa GenerarCadena2 és només una quantitat fixa més gran que la cadena que retorna. De la mateixa manera, canviant la cadena que retorna aquest programa és fàcil de veure que aquest increment és constant.

Teorema: Hi ha una constant c tal que:

$\forall s.K(s)\leq |s|+c$ .

Incomputabilitat de la complexitat de Kolmogórov

Un intent naïf d'un programa per calcular K

A primera vista pot semblar trivial escriure un programa que computi K(s) per a qualsevol s, com per exemple:

funció ComplexitatDeKolmogorov (cadena s)
per i = 2 fins infinit:
per cada cadena p de longitud exactament i:
si ésUnProgramaValid(p) i evaluar(p) == s
retorna i

Aquest programa itera per tots els programes possibles començant amb els més curts i continuant amb programes cada vegada més grans. Després (si és un programa vàlid, és a dir, que el programa corre) l'executa i comptarà la seva sortida a la cadena de la qual volem calcular la seva complexitat. En cas que trobi un programa que funcioni retorna la longitud d'aquest programa.

Tot i això, aquest programa no funcionarà, ja que alguns dels programes p que provarà no pararan, per exemple si contenen bucles infinits. No hi ha cap manera d'evitar aquests programes que no sigui executar-los i esperar que finalitzin a causa de la incomputabilitat del problema de la parada.

Encara més, no hi ha cap programa que calculi K(s), sense importar que tan sofisticat sigui. Això es pot demostrar de la manera següent.

Prova formal de la incomputabilitat de K

Teorema: existeixen cadenes de caràcters d'una complexitat de Kolmogórov arbitràriament gran. Formalment per cada $n\in \mathbb {N}$ existeix una cadena s amb K(s) ≥ n.

Prova: Si això no es complís, llavors les infinites cadenes de longitud finita podrien ser generades pels finits programes de longitud menor a n.

Teorema: K no és una funció computable, és a dir, no hi ha cap programa que donada una cadena s, doni com a resultat K(s).

En la següent prova de contradicció s'utilitza un llenguatge de pseudocodi que per simplificar se suposarà que té un intèrpret de 1000000 bits. Assumeix que existeix un programa

funció ComplexitatDeKolmogorov(cadena s)

que donada una cadena s retorna K(s). Com el programa és finit, per simplificar se suposarà que és de longitud 9000000000 bits ( $9 \cdot 10⁹$ bits). Ara considera el següent programa d'una longitud de no més de 64000 bits.

funció GenerarCadenaComplexa()
per i = 1 fins infinit:
per cada cadena s de longitud exactament i:
si ComplexitatDeKolmogorov(s) > 10000000000
retorna s

Utilitzant la funció ComplexitatDeKolmogorov com a subrutina, el programa prova cada cadena, començant per la més curta, fins que arriba a una cadena de complexitat major a 10000000000 bits ( $10¹⁰$ bits), és a dir, una cadena per la qual es necessita un programa d'una mida de 10000000000 bits com a mínim per ser generada. El problema dona com a resultat el fet que el programa que hem fet i ha generat aquesta cadena com a sortida és de tan sols 9001064000 bits, una complexitat menor a la donada per la funció ComplexitatDeKolmogorov, una contradicció. En el cas que la grandària de la funció ComplexitatDeKolmogorov fos menor, la contradicció continua, i si la funció fos major, només seria necessari ajustar el valor de complexitat que estem buscant.

També és possible mostrar la incomputabilitat de K fent una reducció de la incomputabilitat del problema de parada H, ja que K i H són Turing-equivalents.

Regla de la cadena per la complexitat de Kolmogórov

La regla de la cadena per la complexitat de Kolmogórov diu que:

$K(X,Y)\leq K(X)+K(Y|X)+\mathrm {O} (\log(K(X,Y)))$

Enuncia que el programa que produeix X i Y és com a màxim la complexitat d'un programa que produeix X, la d'un programa que produeix Y donada X i un terme logarítmic. Utilitzant aquest fet, és possible definir un concepte anàleg a la informació mútua per la complexitat de Kolmogórov.

Compressió

És simple computar límits superiors per a K(s). Podem comprimir s amb algun mètode, implementar un descompressor en un llenguatge escollit, concatenar el descompressor a s i llavors mesurar la llargada de la cadena de caràcters resultant. Aquesta llargada és la mida d'un arxiu auto extractible en un llenguatge donat.

Una cadena s és compressible per a c si té una descripció de llargada menor a |s| - c bits. Això és equivalent a dir que K(s) ≤ |s| - c. D'altra forma, s és incompressible per c. Es diu que una cadena és incompressible (en general) si aquesta és incompressible per a 1, a causa del principi de les caselles, que s'aplica, ja que cada cadena comprimida es descomprimeix a una sola cadena, llavors cadenes incompressibles han d'existir, perquè hi ha $2 n$ cadenes de bits amb llargada n, però només $2 n - 1$ cadenes de bits amb llargada menor a n.

Per a les mateixes raons, moltes cadenes són complexes en el sentit que no poden ser comprimides de forma significativa. La seva K(s) no és gaire més petita que la seva |s|. Fixant una n, hi ha $2 n$ cadenes de bits de llargada n. La distribució de probabilitat uniforme de l'espai d'aquestes cadenes assigna exactament un pes igual de $2 - n$ a cada cadena.

Teorema: Amb la distribució de probabilitat uniforme a l'espai de cadenes de bits de longitud n, la probabilitat que una cadena sigui incompressible per c és almenys 1 − 2^−c+1 + 2⁻ⁿ.

Per demostrar el teorema, tingueu en compte que el nombre de descripcions de longitud no superior a n − c és definit per la sèrie geomètrica:

$1+2+2^{2}+...+2^{n-c}=2^{n-c+1}-1$

Llavors, queden almenys

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

cadenes de bits de longitud n que són incompressibles per c. Per determinar la probabilitat, divideix per $2 n$ .

Teorema de la Incompletesa de Chaitin

Pel teorema mencionat anteriorment (vegeu l'apartat anterior “§ Compressió”), la majoria de les cadenes són complexes en el sentit que no poden ser descrites de cap manera comprimida significativament. Així i tot, resulta que el fet que una cadena concreta sigui complexa no pot ser provat formalment si la complexitat d'aquesta supera un cert llindar. La formalització precisa d'això és la següent. Primerament, fixem un cert sistema axiomàtic S per als nombres naturals. El sistema axiomàtic ha de ser prou potent perquè, per a certes assercions A sobre la complexitat de les cadenes, un pugui associar a la fórmula F_A a S. Aquesta associació ha de tenir la propietat següent:

Si F_A es pot provar a partir dels axiomes de S, llavors la corresponent asserció A deu ser certa. Es pot arribar a aquesta formalització a partir d'un nombre de Gödel.

Teorema: Existeix una constant L (que només depèn de S i de l'elecció del llenguatge de descripció) tal que no existeix cap cadena s per a la qual la declaració K(s) ≥ L es pugui provar a S.

Idea de demostració: La prova d'aquest resultat està modelada sobre una construcció autoreferencial utilitzada a la paradoxa de Berry. Primer obtenim un programa que enumera les proves a S i especifiquem al procediment P, que pren com a entrada un nombre enter L i imprimeix les cadenes x, que són dins les proves dins d'S de la declaració K(s) ≥ L. Si llavors establim L major que la longitud d'aquest procediment P, trobem que la longitud requerida per a un programa que imprimeixi x valdrà menys que L (tot i que la declaració K(s) ≥ L, estableixi que ha de valdre almenys L). Hem arribat a una contradicció. Per tant, la demostració del sistema S no pot provar K(s) ≥ L per a valors de L arbitràriament grans, en particular, per a L major que la longitud del procediment P (que té una mida finita).

Demostració:

Podem trobar una enumeració de totes les demostracions formals a S a partir d'un cert procediment

funció N-èssimaDemostració(numero n)

que pren com a entrada n i retorna una demostració. Aquesta funció enumera totes les demostracions. Algunes d'aquestes demostracions per a fórmules ens resulten irrellevants ara mateix, ja que totes les demostracions possibles en el llenguatge de S es produeixen per a alguns n. Algunes d'aquestes són fórmules de complexitat de la forma K(s) ≥ n on s i n són constants en el llenguatge de S. Hi ha un procediment

funció DemostracióN-èssimaDemostraFormulaDeComplexitat(numero n)

que determina si l'enèsima demostració demostra realment una fórmula de complexitat K(s) ≥ L. Les cadenes s, i l'enter L, respectivament, són computables pel procediment:

funció CadenaDeN-èssimaDemostració(numero n)

funció FitaInferiorDeComplexitatDeN-èssimaDemostració(numero n)

Considereu el procediment següent:

funció GeneraCadenaDemostrablementComplexa(numero n)
per i = 1 fins infinit:
si DemostracióN-èssimaDemostraFormulaDeComplexitat(i) i FitaInferiorDeComplexitatDeN-èssimaDemostració(i) ≥ n
retorna CadenaDeN-èssimaDemostració(i)

Donada una n, aquest procediment prova totes les demostracions fins que troba una cadena i una demostració en el sistema formal S de la fórmula K(s) ≥ L per a algun L ≥ n; si no existeix aquesta prova, continuarà al bucle per sempre.

Finalment, considereu el programa que consta de totes aquestes definicions de procediment i una convocatòria principal:

GeneraCadenaDemostrablementComplexa(n₀)

on la constant n₀ es determinarà més endavant. La longitud total del programa es pot expressar com U+log₂(n₀), on U és una constant i log₂(n₀) representa la longitud del valor enter n₀, sota la suposició raonable que està codificat en dígits binaris. Escollirem n₀ com a major que la longitud del programa, és a dir, tal que n₀ > U+log₂(n₀). Això és clarament cert per a n₀ prou gran, perquè el costat esquerre creix linealment en n₀ mentre que el costat dret creix logarítmicament en n₀ fins a la constant fixada U.

Aleshores no es pot obtenir cap prova de la forma “K(s) ≥ n” amb L ≥ n₀ a S, com es pot veure amb una reducció a l'absurd: si FitaInferiorDeComplexitatDeN-èssimaDemostració(i) podria retornar un valor ≥ n₀, aleshores el bucle dins de GeneraCadenaDemostrablementComplexa acabaria finalment, i aquest procediment retornaria una cadena s tal que

	K(s)
≥	n₀	per construcció de `GeneraCadenaDemostrablementComplexa`
>	U+log₂(n₀)	per l'elecció de n₀
≥	K(s)	ja que s va ser descrit pel programa amb aquesta longitud

Això és una contradicció, Q.E.D.

Com a conseqüència, el programa anterior, amb el valor escollit de n₀, ha de continuar per sempre.

S'utilitzen idees similars per demostrar les propietats de la constant de Chaitin.

Longitud mínima de missatge

El principi de longitud mínima del missatge d'inferència estadística i inductiva i aprenentatge automàtic va ser desenvolupat per C.S. Wallace i D.M. Boulton el 1968. Minimum message length és bayesià. Té les propietats desitjables d'invariància estadística, consistència estadística i eficiència. C.S. Wallace i D.L. Dowe (1999) va mostrar una connexió formal entre MML i la teoria algorítmica de la informació (o complexitat de Kolmogórov).

Aleatorietat de Kolmogórov

L'aleatorietat de Kolmogórov defineix una cadena (normalment de bits) com a aleatòria si i només si cada programa informàtic que pot produir aquesta cadena és almenys tan llarg com la mateixa cadena. Per a exemplificar aquesta qualitat s'ha d'especificar l'ordinador (o màquina universal de Turing) i el tipus de programa.

Una cadena aleatòria en aquest sentit, es considera incompressible, de forma que no es pot comprimir a un programa de longitud menor que la mateixa cadena.

Per a cada ordinador, hi ha com a mínim una cadena de caràcters aleatòria de Kolmogórov per a cada longitud de cadena.

Que una cadena donada sigui aleatòria depèn de l'ordinador específic escollit. Ja que un ordinador podria tenir una cadena aparentment aleatòria hard-coded de forma que aquesta sigui accessible de forma fàcil amb una cadena més curta.

Relació amb l'Entropia

Per a sistemes dinàmics, la taxa d'entropia i la complexitat algorítmica de les trajectòries estan relacionades per un teorema de Brudno, que la igualtat K(x; T) = h(T) es manté per gairebé totes les x.

Es pot demostrar que per a la sortida de les fonts d'informació de Markov, la complexitat de Kolmogorov està relacionada amb l'entropia de la font d'informació. Més precisament, la complexitat de Kolmogorov de la sortida d'una font d'informació de Markov, normalitzada per la longitud de la sortida, convergeix gairebé amb seguretat (a mesura que la longitud de la sortida va fins a l'infinit) a l'entropia de la font.

Referències

↑ Kolmogorov, Andrey «On Tables of Random Numbers». Sankhyā Ser. A., 25, 1963, pàg. 369–375.
↑ Kolmogorov, Andrey «On Tables of Random Numbers». Theoretical Computer Science, 207, 2, 1998, pàg. 387–395. DOI: 10.1016/S0304-3975(98)00075-9.

Bibliografia

Blum, M. «On the size of machines». Information and Control, 11, 3, 1967, pàg. 257. DOI: 10.1016/S0019-9958(67)90546-3.
Brudno, A. Entropy and the complexity of the trajectories of a dynamical system., Transactions of the Moscow Mathematical Society, 2:127{151, 1983.
Cover, Thomas M. and Thomas, Joy A., Elements of information theory, 1st Edition. Nova York: Wiley-Interscience, 1991. ISBN 0-471-06259-6. 2nd Edition. Nova York: Wiley-Interscience, 2006. ISBN 0-471-24195-4.
Lajos, Rónyai and Gábor, Ivanyos and Réka, Szabó, Algoritmusok. TypoTeX, 1999. ISBN 963-279-014-6
Li, Ming; Vitányi, Paul An Introduction to Kolmogorov Complexity and Its Applications. Springer, 1997. ISBN 978-0387339986.
Yu Manin, A Course in Mathematical Logic, Springer-Verlag, 1977. ISBN 978-0-7204-2844-5
Sipser, Michael, Introduction to the Theory of Computation, PWS Publishing Company, 1997. ISBN 0-534-95097-3.

P. Grunwald, M. A. Pitt and I. J. Myung (ed.), Advances in Minimum Description Length: Theory and Applications, M.I.T. Press, April 2005, ISBN 0-262-07262-9.

Universal AI based on Kolmogorov Complexity ISBN 3-540-22139-5 by M. Hutter: ISBN 3-540-22139-5

Vegeu també

Enllaços externs

[1] Kolmogorov, Andrey «On Tables of Random Numbers». Sankhyā Ser. A., 25, 1963, pàg. 369–375.

[2] Kolmogorov, Andrey «On Tables of Random Numbers». Theoretical Computer Science, 207, 2, 1998, pàg. 387–395. DOI: 10.1016/S0304-3975(98)00075-9.

[1]

[2]