В каком классе находятся рандомизированные алгоритмы, которые ошибаются с вероятностью 25%?

Предположим, я рассматриваю следующий вариант BPP, который позволяет нам называть E (xact) BPP: язык находится в EBPP, если существует рандомизированный TG за полиномиальное время, который принимает каждое слово языка с вероятностью 3/4 и каждое слово не в язык с вероятностью 1/4. Очевидно, что EBPP содержится в BPP, но равны ли они? Это было изучено? Как насчет аналогично определяемой ERP?

Мотивация. Моя главная мотивация заключается в том, что я хотел узнать, что такое теоретический аналог сложности рандомизированного алгоритма "правильное ожидаемое значение" Faenza et al. (см. http://arxiv.org/abs/1105.4127 ) будет. Сначала я хотел понять, какие задачи решения может решить такой алгоритм (с наихудшим полиномиальным временем выполнения). Обозначим этот класс через E (ожидаемое) V (alue) PP. Легко видеть, что USAT $\in$ EVPP. Также легко увидеть, что EBPP $\subset$ EVPP. Так что это была моя мотивация. Любые отзывы о EVPP также приветствуются.

На самом деле их алгоритм всегда выводит неотрицательное число. Если мы обозначим задачи решения, распознаваемые таким алгоритмом, через EVP (положительный) PP, то у нас все еще будет USAT $\in$ EVPPP. Хотя EBPP не может быть подмножеством EVPPP, у нас есть ERP $\subset$ EVPPP. Возможно, используя их, мы можем определить (неотрицательный) ранг для решения проблем.

С другой стороны, не ясно, что EBPP является устойчивым классом. Например, если вместо того, чтобы позволить алгоритму перевернуть несмещенную монету, если ему дали несмещенную 3-стороннюю монету или 6-сторонний кубик, не ясно, что вы получаете тот же класс. BPP остается прежним, если вы измените эти данные.

В любом случае, ваш основной вопрос - равен ли EBPP BPP или нет. Мне кажется, что EBPP ближе к P, чем к BPP. Рассмотрим сложность запроса или версию оракула этих классов, где они имеют доступ к большой входной строке и должны выполнять запросы для изучения битов этой строки. Если у вас есть алгоритм P, вычисляющая функцию с Q запросов, то существует точная представляющая многочлен степени Q для F над R . (Это обычный аргумент метода полинома.) С другой стороны, если у вас есть алгоритм BPP, то вы получите многочлен степени Q над R, который приближается к $f$$Q$$Q$$f$$\mathbb{R}$$Q$$\mathbb{R}$$f$в том смысле, что его значение близко к значению на каждом входе.$f$

Учитывая алгоритм EBPP для функции , мы можем построить многочлен, который выдает 1/4, если ответ НЕТ, и 3/4, если ответ ДА. Вычитая 1/2 и умножая на 2, вы можете получить точное представляющее многочлен, как в случае с P. Это наводит меня на мысль, что EBPP ближе к P.$f$

Это наблюдение также может быть использовано для демонстрации разделения оракула между EBPP и BPP. Рассмотрим проблему «обещание-большинство», когда вам обещают, что вход имеет более 2N / 3 1s или меньше N / 3 1s, и вам нужно решить, в каком случае. Это явно в БПП. Используя полиномиальный аргумент, описанный выше, можно показать, что эта функция требует запросов для машины EBPP. Но учтите, что вы также можете доказать разделение оракула другим способом, между P и EBPP. Так что, возможно, результаты оракула мало что говорят об этой проблеме? Или, может быть, они говорят, что будет трудно показать равенство в любом направлении.$\Omega(N)$

Что касается разделения оракула, существует оракул с EBPP = BPP = EXP ^NP и оракул с P = ⊕P (и, следовательно, EBPP = P) и BPP = EXP ^NP .

Одно из построений оракула BPP = EXP ^NP (в том числе в статье Википедии о BPP ) состоит в том, чтобы выбрать релятивизированную задачу завершения EXP ^NP и рекурсивно перейти к входному размеру (для этой проблемы), исправить результаты для проблемных экземпляров такого размера и затем предоставьте ответы на эту проблему, если запросите ввод и заполнитель (соответствующей длины), который не был исправлен. Для EBPP = EXP ^NP , вместо того, чтобы почти всегда давать правильные ответы, мы можем дать только достаточно неправильных ответов, чтобы подсчитать точно. Существует также оракул, в котором аналог EBPP с нулевой ошибкой (ровно 1/2 вероятности сообщения об ошибке) равен EXP (и оракулу с P = ⊕P, но ZPP = EXP).

P = ⊕P и БПП = EXP ^NP оракул отмечается здесь .

Помимо BPP и C ₌ P, EBPP находится в ⊕P, поскольку мы можем уменьшить вероятность до числа свидетелей, а затем настроить это число.

В нерелятивизированном мире BPP, вероятно, равен P, но доказательства для EBPP еще сильнее. EBPP зависит от точного числа путей таким образом, что, если не произойдет неожиданное отмены, кажется практически невозможным использовать.

Это частичный ответ; может быть, это вдохновит кого-то другого на предоставление лучшего. $\newcommand{\EBPP}{\mathsf{EBPP}}$ $\newcommand{\CP}{\mathsf{C}_=\mathsf{P}}$

Ваш класс является частным случаем C = P . Я думаю, что один из способов определения C = P заключается в следующем (см. Раздел 2 этой статьи ). Язык L находится в C = P, если существует полиномиальный верификатор времени V такой, что$\EBPP$$\CP$$\CP$$L$$\CP$$V$

• если находится в L , то Pr w [ V ( x , w )  принимает ] = $x$$L$ и$\Pr_w[V(x, w) \text{ accepts}] = \frac{3}{4}$
• если не в L , то Pr w [ V ( x , w )  принимает ] ≠ $x$$L$ .$\Pr_w[V(x, w) \text{ accepts}] \neq \frac{3}{4}$

(Вероятность полноты может быть любой фиксированной дробью; я выбрал чтобы оно соответствовало вероятности, указанной в вашем вопросе.)$\frac{3}{4}$

Один из способов определения заключается в следующем. Язык L находится в E B P P, если существует полиномиальный верификатор времени V такой, что$\EBPP$$L$$\EBPP$$V$

• если находится в L , то Pr w [ V ( x , w )  принимает ] = $x$$L$ и$\Pr_w[V(x, w) \text{ accepts}] = \frac{3}{4}$
• если не в L , то Pr w [ V ( x , w )  принимает ] = $x$$L$ .$\Pr_w[V(x, w) \text{ accepts}] = \frac{1}{4}$