Использование колмогоровской сложности в качестве входного «размера»

21

S

I(n)={wS:|w|=n}
nT(w)AwA
fn=maxwI(n)T(w).

Теперь определим множества всех входов со сложностью Колмогорова и определим последовательность Здесь - средняя последовательность времени выполнения для , за исключением случаев, когда «размер» входных данных представляет собой их колмогоровскую сложность, а не их длину.n f K n = 1

IK(n)={wS:K(w)=n}
nfKA
fnK=1|IK(n)|wIK(n)T(w).
fKA

Существуют ли алгоритмы, для которых асимптотически существенно отличается от ? Если да, то есть ли проблемы, временная сложность которых меняется при использовании этого другого способа анализа алгоритмов?е К пfnfnK

Андрей
источник
4
Отличный вопрос! Я часто задавался вопросом - надеюсь, он получит хорошие ответы. (Я добавил тег параметризованной сложности b / c, вы можете рассматривать это как вопрос параметризованной сложности, например, SAT, где параметром является сложность Колмогорова.)
Джошуа Грохов
3
Случайные строки, то есть большинство строк, имеют колмогоровскую сложность около своей первоначальной длины. Для подавляющего большинства входных данных Вы можете получить более интересный результат, если спросите о вычислительной глубине, а не о колмогоровской сложности. google.com/…fn=fnK
Чад Брюбейкер
2
Путем смешивания в некоторых случаях PARITY с жестким языком для формирования (например, путем добавления к каждому экземпляру префикса с битовым переключателем, который описывает, с какого языка этот экземпляр), тогда будет меньше, чем . Как мало, зависит от относительной плотности. f K n f nSfnKfn
Андраш Саламон
1
Одно место в лекциях Вадхана здесь (19 февраля): people.seas.harvard.edu/~salil/cs221/spring10/lectures.html
usul
1
@ AndrásSalamon, да, надеюсь, я не слишком небрежен, но я думаю, чтопо сути должна быть функция занятого бобра. nmaxw:K(w)=n|w|
usul

Ответы:

14

Рассмотрим функцию контроля четности (или любую другую функцию, которая зависит от всех / большинства битов ввода). Для функции четности . Так что С другой стороны, f n = Θ ( n ) . f K n = Θ ( 1T(w)=Θ(|w|)

fn=Θ(n).
fnK=Θ(1|IK(n)|w:K(w)=n|w|)Ω(12nmaxw:K(w)=n|w|).

Обратите внимание, что . Таким образом, и . Аналогично, ; таким образом, «растет очень быстро». Более того, нетрудно видеть, что для нет вычисляемой верхней границы .max w : K ( w ) = n | ш | 2 2 Ω ( n ) f K n2 2 Ω ( n ) / 2 nK ( 2 2 2 n ) = O ( n ) f K nK(22n)=O(n)

maxw:K(w)=n|w|22Ω(n)
fnK22Ω(n)/2nK(222n)=O(n)f K nfnK222Ω(n)/2nfnK
Юрий
источник
9

Учитывая интерес к этому вопросу, я подумал, что было бы полезно более четко указать причину, по которой мы вообще не должны удивляться ответу, и попытаться дать некоторые указания для уточнения вопроса. Это собирает и расширяет некоторые комментарии. Прошу прощения, если это "очевидно"!

Рассмотрим множество струн колмогоровской сложности : Таких строк не более , так как имеется описание длины . Но обратите внимание, что это множество неразрешимо для общего (в противном случае мы могли бы вычислить просто выполнив итерацию от до и проверив членство в ). Кроме того, функция растет неисчислимо быстро. Это вариант функции «занятый бобер»: какой самый длинный вывод машины Тьюринга с длиной описанияn

JK(n)={w:K(w)=n}.
2n2nnnK(w)n=1|w|JK(n)
gK(n)=maxwJK(n)|w|
n? Если бы это росло медленнее, чем какая-то вычислимая функция, мы могли бы решить проблему остановки: с учетом TM построить который имитирует и печатает на каждом шаге. Если длина описания равна , то либо: останавливается не более чем за шагов; или не останавливается.MMM1MnMgK(n)M

Теперь, к вопросу Эндрю, мы имеем, что , где - исходный язык. Таким образом, единственный способ избежать содержащего входы, очень большие по это если содержит только очень несжимаемые строки. (Обратите внимание, что в противном случае мы можем полностью игнорировать различие между наихудшим и средним случаями анализа, потому что мы усредняем не более строк, но размер самой большой строки растет быстрее, чем любая вычислимая функция . )IK(n)=SJK(n)SIK(n)nS2nn

Я чувствую, что, вероятно, невозможно построить какой-либо нетривиальный (т. Е. Бесконечный) , содержащий только несжимаемые строки, но разрешимый. Но я не знаю Однако, надеюсь, это дает интуицию относительно того, почему мы не должны надеяться, что большинство языков будут иметь растущий медленнее, чем вычислимая функция.SfnK

Чтобы немного отступить, вопрос заключается в сравнении производительности на входах длины с производительностью на входах, которые могут быть сжаты до длины . Но у нас есть представления о сжатии, которые гораздо более податливы (и менее мощны), чем сложность Колмогорова. Простой способ - получить схему размером , которая на входе двоичного числа выдает й бит . Обратите внимание, что здесь увеличение входного размера является не более экспоненциальным (схема размером имеет не более возможных входов).nnnbbwn2n

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

IC(n)={wS:the smallest circuit implicitly specifying w has size n}.
fnCfnfnC

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

IMPLICIT_SAT={circuits C:C implicitly specifies w,wSAT}.
wwfnC=Θ(fn)w"не входит в игру для неявных языков.

Надеюсь, что это полезно / интересно!

Я не уверен в учебнике, который упоминает неявные проблемы, но вот некоторые примечания к лекции: http://people.seas.harvard.edu/~salil/cs221/spring10/lec8.pdf

усул
источник
|JK(n)|=2n ? Но не каждое описание минимально.
Андрей
1
@ AndrewMacFie, верно, должно быть "максимум". Починю.
Усул
Спасибо за добавление этого ответа :) Похоже, что для любого алгоритма для 3-SAT, будет быстро расти. fnK
Андрей
4

Кажется, простой случай, когда язык содержит только дополненные экземпляры. Когда получается из языка путем наложения каждого экземпляра размера с символов, может быть в области .S L n 2 n - n f K n 2 f nSSLn2nnfnK2fn

Андраш Саламон
источник
Обратите внимание, что ответ Юрия включает этот ответ, а также уточняет «может быть в районе».
Андрас Саламон