Можно ли заменить истинную случайность (доказуемо) случайностью Колмогорова для RP?

Были ли попытки показать, что колмогоровской случайности было бы достаточно для RP ? Будет ли вероятность, использованная в утверждении «Если правильный ответ ДА, то она (вероятностная машина Тьюринга) возвращает ДА с вероятностью ...» всегда будет правильно определена в этом случае? Или для этой вероятности будут только верхние и нижние границы? Или всегда будет существовать некоторая вероятностная машина Тьюринга, для которой вероятности будут четко определены (или, по крайней мере, нижняя граница, которая должна быть больше 1/2)?

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

Осмысление слова «вероятность» было бы частью попытки показать, что случайность по Колмогорову работает на RP. Однако позвольте мне попытаться описать один из возможных подходов, чтобы уточнить, что это может означать и почему я говорил о верхних и нижних границах:

Пусть - (случайная по Колмогорову) строка. Пусть - заданная вероятностная машина Тьюринга, соответствующая языку из RP. Запустите с качестве источника для случайных битов раз, продолжая использовать ранее неизрасходованные биты из один за другим. $s$ $A$ $A$ $s$ $n$ $s$

Для $p_n^s:=\frac{\text{#YES result in first $n$ runs of $A$ on $s$}}{n}$ $p_+^s:=\limsup_{n\to\infty}p_n^s$ $p_-^s:=\liminf_{n\to\infty}p_n^s$ $p_+^s$ $p_-^s$ $s$ $p_+^s=p_-^s$ $s$ $p_-^{s_1}=p_-^{s_2}$ $s_1$ $s_2$ $p\geq 1/2$ $p\leq p_-^s$ $s$

randomized-algorithms randomness pseudorandomness Томас Климпел
источник

Я не понимаю вопроса. Что вы подразумеваете под "<понятие случайности> достаточно для <класса сложности>"? RP может быть дерандомизирован за полиномиальное время с оракулом для случайной строки Колмогорова, если это то, что вы спрашиваете.

Эмиль Йержабек

Я не понимаю, что вы имеете в виду, говоря, что RP будет «работать», и я не понимаю ваш последний комментарий (машины RP всегда останавливаются после полиномиального множества шагов, либо по определению, либо без потери общности при использовании неудобного определение).

Эмиль Йержабек

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

Эмиль Йержабек

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

s

$s$

A

$A$

s

$s$

s

$s$

p_{+}

$p_+$

p_{-}

$p_-$

Эндрю Морган

Соответствующие ссылки Википедии (которые имеют дальнейшие ссылки) для моего предыдущего комментария: конструктивный Мартингалес (см. Третье определение) и ограниченная ресурсами мера

Эндрю Морган

Ответы:

Я думаю, что вопрос, который здесь задают, примерно такой: «Есть ли смысл, в котором мы можем заменить последовательность случайных битов в алгоритме битами, детерминированно взятыми из подходящей длинной колмогоровской случайной строки? » ответ! (Краткий ответ: «Да, но только если вы сначала увеличите вероятность ошибки»)

Да...

Мы, конечно, можем что-то сказать здесь. Пусть - некоторый язык, и пусть - алгоритм, который принимает в качестве входных данных и случайную строку (равномерное распределение по ) st . Другими словами, - это алгоритм, который ошибается с вероятностью не более . $L$ $A$ $x$ $r\in U_{f(|x|)}$ $\{0,1\}^{f(|x|)}$ $\Pr[A(x,r)=L(x)]>1-\epsilon(x)$ $A$ $\epsilon(\cdot)$

Теперь обратите внимание, что если дает неправильный ответ на т. Е. , это дает нам некоторые средства описания , в частности, мы можем описать его как -я строка, которая заставляет ошибаться наДля этого мы просто создаем машину, в которой жестко заданы , , и бит , и просто перечисляем варианты из пока не найдет выбор такой, что . $A$ $(x,r)$ $A(x,r)\not=L(x)$ $r$ $i$ $A$ $x.$ $x$ $A$ $i$ $b=1\iff x\in L$ $r'$ $\{0,1\}^{f(|x|)}$ $i$ $r'$ $A(x,r')\not= b$

Итак, теперь, когда мы знаем, что можем использовать неправильный выбор случайной строки в описании, давайте рассмотрим некоторые условия, достаточные для превращения нашего описания в сжатие. Чтобы описать , нам требуется достаточно битов для описания , , , а затем кода для нашей процедуры (код для и описанная нами процедура), дающих в качестве описания длины $r$ $r$ $x$ $i$ $b$ $A$

| x | + | i | + O (1) = | x | + \log_{2} (2^{f (| x |)} ϵ (x)) + O (1) = | x | + f (| x |) - \log (1 / ϵ (x)) + O (1) .

$|x|+|i|+O(1)=|x|+\log_2(2^{f(|x|)}\epsilon(x))+O(1)=|x|+f(|x|)-\log(1/\epsilon(x))+O(1).$

Напомним, что это длина , так что это сжатие если например, когда . $r$ $f(|x|)$ $r$

\log (1 / ϵ (x)) = | x | + ω (1),

$\log(1/\epsilon(x)) = |x|+\omega(1),$

ϵ (x) = 1 / 2^{2 | x |}

$\epsilon(x)=1/2^{2|x|}$

Наконец, обратите внимание, что если бы была случайной строкой Колмогорова, то у нас не могло бы быть такого сжатия, так как, если вероятность ошибки достаточно мала, случайная строка Колмогорова вместо последовательности случайных битов заставит ответить правильно! $r$ $A$ $A$

Обратите внимание, что единственное, что мы используем в - это малая вероятность ошибки. Нам не важно, имеет ли очень длительное время выполнения, или если имеет одну или две односторонние ошибки. $A$ $A$ $A$

Возвращаясь к вопросу о (или или ), это говорит о том, что до тех пор, пока мы усиливаем вероятность ошибок наших алгоритмов, мы можем использовать случайные последовательности Колмогорова вместо их случайных битов. $RP$ $coRP$ $BPP$

... Но только если мы усилим в первую очередь.

Следующим вопросом может быть «могу ли я сделать это без усиления вероятности ошибки?» Рассмотрим следующий алгоритм который решает и имеет вероятность ошибки . $A$ $\{0,1\}^*$ $1/2^n$

На входе : $x$

Создать строку $r\in\{0,1\}^n$
Если , отклонить. $r=x$
Принять.

Обратите внимание, что для каждого выбора существует некоторый выбор такой что ошибается на , а именно выбор который равен , поэтому мы не можем заменить случайную последовательность битов, используемых случайной строкой Колмогорова без усиления это вероятность ошибки! $r$ $x$ $A$ $x$ $r$ $x$ $A$

Примечание об источнике: я не уверен, является ли что-то из этого новым, но я включил первый аргумент в мою рецензию на мой квалификационный экзамен, который в конечном итоге будет доступен онлайн после того, как я закончу его пересматривать.

Дилан Маккей
источник

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

M

$M$

M (x)

$M(x)$

x \in L

$x\in L$

Дилан Маккей

Майк Сипсер использовал аналогичные аргументы сжатия в своей классной статье sciencedirect.com/science/article/pii/0022000088900359 (имейте в виду, что необходимые ему графы расширителей действительно были явно построены dl.acm.org/citation.cfm?id=273915 )

Райан Уильямс