Complexitat de Kolmogórov
From Wikipedia, the free encyclopedia
En la teoria de la computació, la complexitat de Kolmogórov és una mesura de la quantitat de recursos computacionals necessaris per poder descriure una certa quantitat d'informació, deu el seu nom a Andréi Kolmogórov. La complexitat de Kolmogórov també es denomina complexitat descriptiva o complexitat de Kolmogoróv-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]