Про теорию сложности

[akor168]

Сложная эта штука теория сложности.

http://polit.ru/article/2014/03/04/shen_about_kolmogorov/

Вот вроде бы само определение Колмогоровской сложности очень естественно. Однако у меня всегда был затык уже на этапе - а что такое программа языка относительно которого вычисляется, и как оно соотносится с практикой.

Но это все вообще непринципиально. Мне другое интересно всегда было - что можно сказать об колмогоровской сложности больших упорядоченных массивов информации, вроде художественных фильмов или текстов. И как это соотносится с результатами стандартных архиваторов. Вот чисто интуитивно - колмогоровская сложность фильма должна быть гораздо меньше просто набора несвязанных картинок. Но вот насколько меньше...

Comments

[ygam.livejournal.com]

http://en.wikipedia.org/wiki/Hutter_Prize