Ожидаемые значения колмогоровской сложности в случайной выборке

9

Колмогоровская сложность строки не вычислима. Тем не менее, в случайном подмножестве размераM двоичных строк длины Nсколько ожидается, что сложность будет меньше целого числа N0 меньше, чем N (как функция M, N а также N0)?

против
источник
Вы используете здесь «стандартную» колмогоровскую сложность или префиксную сложность?
Обри да Кунья
На самом деле я думал только о колмогоровской сложности. Я угадал2Nосвязано, что domotorp упоминается, когда мы рассматриваем вселенную всех струн. Мне не было ясно, есть ли какой-либо «непротиворечивый» результат для произвольного случайного подмножества размераMможет быть произведено. Однако приведет ли сложность префикса к другой точке зрения?
против
Это, конечно, не изменило бы порядок величины, фактически я думаю, что теперь мой ответ ограничен для обеих версий.
Domotorp
1
Для каждого N и каждый свероятность того, что случайный N-битная строка Икс имеет колмогоровскую сложность К(Икс)N-с больше, чем 1-12ссзнак равноN-N0). Так в случайном распределенииM строки, вы должны ожидать M2(nn0) строки с K(x)<n0... интуитивно, существует очень высокая вероятность выбрать строку с высокой колмогоровской сложностью.
Марцио Де Биаси

Ответы:

10

Сложность по Колмогорову определяется только с точностью до некоторой аддитивной константы, поэтому точного ответа дать невозможно. Граница, которую я здесь опишу, еще слабее.

Конечно, ожидаемое число может быть легко вычислено, когда мы узнаем, сколько 2N строки имеют сложность меньше, чем N0Итак, позвольте мне ответить на это. Обычно это первое утверждение о колмогоровской сложности, что это число не более2N0-1- поскольку есть только эти много строк меньшей длины. С другой стороны, если ваша программа говорит «о длинеNвозьми Иксй номер ", тогда вы получите 2N0-К(N)-С строки сложности меньше N0, где К(N) безфиксная версия колмогоровской сложности N (так максимум журналN+журнал*N+О(1)). Более подробно, строка сначала содержит описание машины Тьюринга, которая приняла вводпИксгде p - описание программы без префиксов, которая выводит Nвыводит Иксномер длины N, который О(1) биты, а затем за этим следует пИкс,

Возможно, можно улучшить эти границы, но я сомневаюсь, что вы могли бы получить точный ответ.

domotorp
источник
Не могли бы вы немного объяснить фразу «если ваша программа говорит« длины n, возьмите x-е число »»?
против
Вы правы, там должно быть без префиксов, я это исправил.
Domotorp
3

Точный ответ может быть дан. Количество строк длиныN с (простой) сложностью N0 является 2N0-К(N0|N)с точностью до постоянного фактора. Следовательно, любой процесс, который случайным образом выбирает подмножество, будет иметь с разумной вероятностью2-К(N0|N)+О(1) доля строк сложности меньше N0, Для того, чтобы показать наше наше утверждение, достаточно показать , что число строк со сложностью равных сК также дается 2К-К(К|N), Мы можем показать необходимый результат, определив суммирование этого значения заК от 1 до N0, Чтобы показать это, мы используем результат аддитивности для простой сложности (из-за Б. Бауенса и А. Шена. Теорема аддитивности для простой сложности Колмогорова . Теория вычислительных систем, 52 (2): 297-302, февраль 2013 г.),

C(a,b)=K(a|C(a,b))+C(b|a,C(a,b))+O(1),
Вот K()обозначает без префикса колмогоровскую сложность. Выборa=nмы наблюдаем, что для каждого n-битная строка b сложности k у нас есть
k=C(b)=C(n,b)+O(1)=K(n|k)+C(b|n,k)+O(1).
Следовательно, для каждого такого b у нас есть C(b|n,k)=kK(n|k)+O(1), Позволятьk=kK(n|k), Теперь можно наблюдать, что их максимумO(2k) такие строки bи каждый из лексикографически первых 2k строки длины n удовлетворять C(b|n,k)k+O(1), таким образомΩ(2k) из них удовлетворяют C(b|n,k)=k+O(1),
Бруно Баувенс
источник