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

[akor168]

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

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

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

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

Comments

[ygam.livejournal.com]

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

[akor168.livejournal.com]

В курсе, и отчасти мотивация для вопроса.

Меня собственно удивляет, что ничего кроме весьма узкого круга алгоритмов(назовем их частотными), для общего сжатия данных(без потерь) так и не придумано. Насколько я понимаю, есть примеры генерации больших массивов информации, простой программой(то есть заведомо низкой колмогоровской сложности), которые не сжимаются Зипами и Рарами.

[ygam.livejournal.com]

Конечно: генератором псевдослучайных чисел.

[akor168.livejournal.com]

В том числе. Интересно другое. Есть любопытная связь колмогоровской сложности строки с количеством возможных представлений этой строки(на множестве которых вводится псевдомера которая суммирует все к колмогоровской сложности). В некотором смысле - если у строки есть малая сложность, то у нее есть очень много больших представлений. Я это интерпретирую так, что хоть алгоритм который по псевдослучайной строке декодирует ее генератор, вряд ли доступен из общих соображений, тем не менее какой-то алгоритм(причем их должно быть много) должен это сжимать, тем не менее.

Ну и второе - реальные данные которые использует человек мало похожи на псевдослучайные. Те архиваторы которые есть сжимают, но не удивлюсь если они сжимают как раз к этому псевдослучайному барьеру, а реальная колмогоровская сложность сильно ниже, и чем сильнее ниже тем больше шансов что какой-то другой алгоритм это сожмет лучше.