Когда BPP с предвзятой монетой соответствует стандартному BPP?

Пусть вероятностная машина Тьюринга имеет доступ к недобросовестной монете, которая выпадает в голову с вероятностью (броски независимы). Определите как класс языков, распознаваемых такой машиной за полиномиальное время. Это стандартное упражнение, чтобы доказать, что: $p$ $BPP_p$

A) Если рационально или даже вычислимо, то . (Под вычислимым я имею в виду: существует рандомизированный полиномиальный алгоритм, который подает в унарных возвращаемых значениях, когда двоичное рациональное число со знаменателем лежит в пределах от .) $p$ $BPP$ $BPP_p=BPP$ $BPP$ $n$ $2^n$ $2^{-n-1}$ $p$

B) Для некоторого невычислимого класс содержит неразрешимый язык и, следовательно, больше, чем . Такие значения образуют плотное множество в . $p$ $BPP_p$ $BPP$ $p$ $(0,1)$

Мой вопрос заключается в следующем: что происходит между ними? Есть ли критерий для ? В частности: $BPP_p=BPP$

1) Существуют ли невычислимые в вероятности такие, что ? (Они могут быть вычислимы в некоторых высших классах). $BPP$ $p$ $BPP_p=BPP$

2) шире, чем для всех невычислимых ? (Рассматриваемые параметры - это те, чье двоичное расширение содержит очень длинные последовательности нулей и / или единиц. В этом случае вычисление битов методом случайной выборки может занять очень много времени, даже не вычисляемое, и проблема не может быть масштабирована до полиномиального времени. Иногда трудность может быть преодолена с помощью другой базы расширения, но некоторые могут обмануть все базы). $BPP_p$ $BPP$ $p$ $p$

cc.complexity-theory randomized-algorithms probabilistic-complexity Даниил Мусатов
источник

Что именно вы подразумеваете под p, будучи (не) вычислимым?

Даниелло

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

B P P

$BPP$

Даниил Мусатов

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

B P P_{p} \neq B P P

$BPP_p \neq BPP$

p

$p$

p

$p$

n

$n$

p

$p$

n

$n$

f (n)

$f(n)$

1^{x}

$1^x$

x

$x$

f^{- 1} (x)

$f^{-1}(x)$

p

$p$

1

$1$

B P P_{p}

$BPP_p$

Даниелло

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

p

$p$

p

$p$

n

$n$

f (n)

$f(n)$

f (n)

$f(n)$

Даниил Мусатов

Ответы:

1) Да, но только из-за вашего определения. Возьмите унарный язык (да, я знаю, что это может быть пустым, в этом случае просто возьмите что-то даже больше, чем ), что очень мало в том смысле, что если не является башня , т. е. в форме . Определите . Это не является вычислимым, но может быть аппроксимировано в до достаточно малой аддитивной ошибки, которая позволяет моделировать машину . $L\in EXP\setminus BPP$ $EXP$ $n\notin L$ $n$ $2's$ $2^{2^{2^\ldots}}$ $p=\sum_{n\in L} 1/n$ $p$ $BPP$ $p$ $P$ $BPP_p$

Если бы вы определили вычислимость так, что вы хотите приблизить до аддитивной ошибки (вместо ) за полиномиальное время, все было бы иначе. $BPP$ $p$ $1/n$ $1/2^n$

Обновить. Ответ ниже для случая, когда допускаемая нами аддитивная ошибка равна вместо . $2^{-n}$ $2^{-n-1}$

2) Да, потому что здесь вы можете забыть о полиномиальном ограничении на классы и, выбрав раз, вы можете получить бит в . $2^n$ $n$ $p$ $BPP_p$

domotorp
источник

2) Я думаю, что центральная предельная теорема предполагает, что для получения точности нужно выбирать , а не раз . Но главная проблема в том, что иногда нам нужна гораздо большая точность. Скажем, если то нужно выборок, чтобы вычислить хотя бы первую цифру. И количество необходимых выборок может быть произвольно, даже неисчислимо, большим. Суть немного прояснена в редактировании.

2^{2 n}

$2^{2n}$

2^{n}

$2^n$

2^{- n}

$2^{-n}$

| p - \frac{1}{2} | < ϵ

$|p-\frac12|<\epsilon$

\frac{1}{ϵ^{2}}

$\frac1{\epsilon^2}$

Даниил Мусатов

@Daniil: Как я уже прокомментировал вопрос, вы не просили вычисление цифр в вашем определении вычислимого. Итак, если равно, скажем, , то нужно угадать для первой цифры после запятой в соответствии с вашим определением.

B P P

$BPP$

p

$p$

0.01111111111

$0.01111111111$

1

$1$

domotorp

Мы сейчас говорим о неисчислимом , не так ли? Если я вас правильно понимаю, вы предлагаете не вычислять путем выборки цифр , а вместо этого вычислять, равна ли -тая цифра двоичной рациональной аппроксимации единице. Но здесь мы сталкиваемся с тем же Задача: чтобы вычислить первую цифру, нам нужно различить 0,010000000001 и 0,001111111110.

p

$p$

p

$p$

i

$i$

2^{- i - 1}

$2^{-i-1}$

p

$p$

Даниил Мусатов

@Daniil: ОК, мой плохой, я думал, что вы хотели двоичный рациональный, чье расстояние не более от . Я обновил свой ответ соответственно. Довольны ли вы моим решением 1)?

2^{- n}

$2^{-n}$

p

$p$

domotorp