Какова самая быстрая из известных симуляций БПП с использованием алгоритмов Лас-Вегаса?

$\mathsf{BPP}$ и $\mathsf{ZPP}$ - два основных класса вероятностной сложности.

$\mathsf{BPP}$ - это класс языков, определяемых вероятностными алгоритмами Тьюринга за полиномиальное время, где вероятность возврата неправильного ответа ограничена, т. Е. Вероятность ошибки не превышает $\frac{1}{3}$ (для случаев ДА и НЕТ).

С другой стороны, алгоритмы $\mathsf{ZPP}$ можно рассматривать как те вероятностные алгоритмы, которые никогда не возвращают неправильный ответ, всякий раз, когда они возвращают ответ, он является правильным. Однако их время выполнения не ограничено полиномом, они работают в ожидаемом полиноме.

Пусть $\mathsf{ZPTime}(f)$ - класс языка, определяемый вероятностными алгоритмами с нулевой вероятностью ошибки и ожидаемым временем выполнения $f$ . Они также называются алгоритмами Лас-Вегаса и $\mathsf{ZPP} = \mathsf{ZPTime}(n^{O(1)})$ .

Мой вопрос: что лучше всего знать симуляцию алгоритмов $\mathsf{BPP}$ с использованием алгоритмов Лас-Вегаса? Можем ли мы смоделировать их в субэкспоненциальном ожидаемом времени? Есть ли какое-либо известное улучшение по сравнению с обычным моделированием грубой силы, которое занимает экспоненциальное время?

Более формально, знаем ли мы, что $\mathsf{BPP} \subseteq \mathsf{ZPTime}(2^{O(n^{\epsilon})})$ или $\mathsf{BPP} \subseteq \mathsf{ZPTime}(2^{n-n^{\epsilon}})$ для некоторого $\epsilon>0$ ?

cc.complexity-theory complexity-classes randomness randomized-algorithms echuly
источник

Что такое n, длина входа? Почему мы можем принять в

2^{n}

$2^n$

domotorp

- это то же самое, что

2^{p o l y (n) - n^{ϵ}}

$2^{\mathrm{poly}(n)-n^\epsilon}$

2^{p o l y (n)}

$2^{\mathrm{poly}(n)}$

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

Я нахожу вопрос довольно интересным. Я отредактировал вопрос, чтобы сделать его более читабельным и точным. Не стесняйтесь редактировать дальше. пс: Я предполагаю , что вы , вероятно , хотел , чтобы принять во внимание полиномиально много случайных битов , используемых алгоритмом БПП в качестве параметра для моделирования времени , но , как Эмиль указывает на то , что вы написали , дает

. Если вы хотите, чтобы вам пришлось заменить BPP определенным классом вероятностных алгоритмов с ограниченной ошибкой, у которых есть параметр для числа случайных битов, используемых алгоритмом.

2^{p o l y (n)}

$2^{poly(n)}$

Каве

Вы можете спросить, можем ли мы смоделировать алгоритм BPP, который использует

случайных битов в

поскольку имитация грубой силы выполняется в

раз.

r (n)

$r(n)$

Z P T i m e (2^{r (n) - n^{ϵ}} n^{O (1)})

$\mathsf{ZPTime}(2^{r(n)-n^\epsilon}n^{O(1)})$

2^{r (n)} n^{O (1)}

$2^{r(n)}n^{O(1)}$

Каве

Ответы:

Во- первых, заметим , что если для некоторой константы , то . (Доказательство - недетерминированная иерархия времени.) Таким образом, доказательство такого включения было бы значительным не только потому, что это улучшенное моделирование, но также дало бы первый прогресс в рандомизированных нижних границах времени за десятилетия. $\mathsf{BPP} \subseteq \mathsf{ZPTIME}[2^{n^{c}}]$ $c$ $\mathsf{BPP} \neq \mathsf{NEXP}$

Далее рассмотрим класс $\mathsf{PromiseBPP}$ , для которых следующая проблема является « -трудной»: $\mathsf{PromiseBPP}$

Схема аппроксимации вероятности Задача (CAPP): Принимая во внимание схему , выход принятие вероятность с точностью до аддитивного фактора. $C$ $C$ $1/6$

$2^{n^{\varepsilon}}$ $n$ $C$ $\mathsf{NEXP} \not\subset \mathsf{P/poly}$ $C$ $k$ $n$ $2^{k-\omega(\log k)}\mathrm{poly}(n)$ $\mathsf{NEXP} \not\subset \mathsf{P/poly}$ , То есть, безусловно, существуют проблемы, которые можно вычислить со случайностью двухсторонних ошибок, для которых алгоритмы с нулевой ошибкой, которые даже слегка опережают исчерпывающий поиск, подразумевают нижние границы схемы. Я считаю, что это следует интерпретировать как возможный метод доказательства нижних оценок; Ваш пробег может варьироваться.

Обратите внимание, что даже доказательство также открыто, и доказательство , которое также подразумевало бы более низкие оценки: Кабанец и Импальяццо 2004, если полиномиальная идентичность тестирование ( проблема ) находится в для всех , тогда у нас есть нижние оценки для постоянного или . Недавно (выйдя в STOC'13) я безоговорочно доказал, что либо или имеет $\mathsf{RP} \subseteq \mathsf{ZPTIME}[2^{n^{\varepsilon}}]$ $\mathsf{coRP}$ $\mathsf{ZPTIME}[2^{n^{\varepsilon}}]$ $\varepsilon > 0$ $\mathsf{NEXP}$ $\mathsf{BPP} \subseteq \mathsf{ioZPTIME}[2^{n^{\varepsilon}}]/n^{\varepsilon}$ $\mathsf{RTIME}[2^n]$ $n^c$ размерная схема, построенная по методу «легкого свидетельства» Кабанца. Это подразумевает две вещи:

Существует такой, что для всех , безусловно находится в - это примерно безусловный дерандомизация в которую мы знаем до сих пор. $c$ $\varepsilon > 0$ $\mathsf{RP}$ $\mathsf{ioZPTIME}[2^{n^{\varepsilon}}]/n^c$ $\mathsf{RP/BPP}$ $\mathsf{ZPP}$
Чтобы начать интересное субэкспоненциальное моделирование , вы «только» должны предположить, что не имеет схем фиксированного полиномиального размера. $\mathsf{BPP}$ $\mathsf{RTIME}[2^n]$

Райан Уильямс
источник

Спасибо Нилу за то, что он нашел время, чтобы сделать мой ответ разборчивым :)

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

Райан, я думаю, что собираюсь задать очень глупый вопрос, но здесь я иду: в вашем первом предложении, зачем вам "для всех "? Разве BPP-подмножество ZPTIME (2 ^ (n ^ c)) для некоторого фиксированного c не подразумевает BPP-подмножество RTIME (2 ^ (n ^ c)) и, следовательно, NTIME (2 ^ (n ^ c)), поэтому BPP не равно NEXP или иначе NTIME (2 ^ (2n ^ c)) является подмножеством NTIME (2 ^ (n ^ c))?

ϵ

$\epsilon$

Сашо Николов

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

B P P \subseteq N T I M E (2^{n^{c}})

$BPP \subseteq NTIME(2^{n^c})$

c

$c$

B P P \neq N E X P

$BPP \neq NEXP$

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

Райан: Если бы я хотел понять вашу статью, с какой книгой / статьями по сложности схем вы бы порекомендовали ознакомиться?

T ....

Привет Арул, к счастью, Билл Гасарч задал мне этот вопрос некоторое время назад и разместил следующую веб-страницу ссылок: cs.umd.edu/~gasarch/ryan/ryan.html

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

Это зависит от того, какие предположения вы готовы сделать.

При определенных предположениях о твердости, а именно , вы получите . Это, в частности, подразумевает, что , и, следовательно, что каждый язык принимается машиной Лас-Вегаса (см. «P = BPP, если E не имеет субэкспоненциальных цепей: дерандомизацию леммы XOR», Impagliazzo и Wigderson). $E \not\subseteq SIZE(2^{\varepsilon n})$ $P = BPP$ $BPP = ZPP$ $L \in BPP$

Вы также можете сделать более мягкое предположение о твердости, а именно, что , и получить (см. Лемму 46 в "В поисках Легкий свидетель: экспоненциальное время против вероятностного полиномиального времени (Импальяццо, Кабанец и Вигдерсон). $ZPE \not\subseteq \rm{io-DTIME}(2^{\varepsilon n})$ $BPP = ZPP$

Или меир
источник

За исключением каких-либо достижений в дерандомизации, мне кажется, что требование, чтобы машина Лас-Вегаса не делала ошибок, было критически важным, так что в этом случае случайность вообще ничтожна.

Для языка BPP определяется подходящим алгоритмом , который действует на входы и случайную строку представляющую При случайном выборе критерий с нулевой ошибкой подразумевается, что машина Лас-Вегаса должна точно определить, какой из двух случаев . Если нам не дают никакой дополнительной информации об , то это, по сути, проблема обещания оракула: дано оракулу вычисление и дано обещание, что $L$ $A$ $x \in \{0,1\}^n$ $r \in \{0,1\}^{N(n)}$

\underset{r}{Pr} (A accepts (x, r)) ⩾ \frac{2}{3} or \underset{r}{Pr} (A accepts (x, r)) ⩽ \frac{1}{3}

$\Pr_r(\text{$A$ accepts $(x,r)$}) \geqslant \tfrac{2}{3} \quad\text{or}\quad \Pr_r(\text{$A$ accepts $(x,r)$}) \leqslant \tfrac{1}{3}$

A

$A$

A^{'}

$A'$

A^{'} (r) = A (x, r)

$A'(r) = A(x,r)$

A^{'}

$A'$ дает один выход как минимум вдвое больше входов, чем противоположный выход , определяет, какой выход является более распространенным.

a \in {0, 1}

$a \in \{0,1\}$

1 - a

$1-a$

Хотя машина Лас-Вегаса может использовать случайные методы, если мы действительно вынуждены рассматривать как оракула, мы можем видеть, что единственной стратегией, доступной машине Лас-Вегаса, является проведение относительно тщательного (хотя и не исчерпывающего) обзора случайные строки , чтобы увидеть, какой ответ дается для каждого. Он может быть уверен, только если найдет более различных строк которые все приводят к одному и тому же результату; в противном случае, с небольшой (но ненулевой!) вероятностью, это может быть неудачно и получить нерепрезентативную выборку возможных выходных данных. Чтобы получить нулевую ошибку, он должен выбрать не менее входов . $A'$ $r$ $2^{N(n)}\!/3$ $r$ $2^{N(n)}\!/3$ $r$

Поскольку машина Лас-Вегаса должна проверять по крайней мере постоянную часть всех возможных случайных строк , асимптотически мы ничем не лучше, чем если бы мы детерминистически протестировали все возможные случайные строки. Мы не получаем никаких асимптотических преимуществ при случайном моделировании алгоритмов BPP в условиях с нулевой ошибкой, помимо того, что мы можем сделать детерминистически методом грубой силы. $r$

Обратите внимание, что этот же аргумент приводит к разделению оракула между BPP и ZPP , то есть существует оракул такой что потому что алгоритм ZPP требует экспоненциального времени, в то время как Алгоритм BPP может решить вопрос о оракуле в одном запросе и добиться успеха с ограниченной ошибкой. Тем не менее, это не говорит вам больше, чем вы уже подозревали (что накладные расходы на моделирование могут быть хуже, чем полиномиальные) или что асимптотика так же плоха, как наивное детерминированное моделирование. $A$

{Z P P}^{A} ⫋ {B P P}^{A}

$\mathsf{ZPP}^A \subsetneqq \mathsf{BPP}^A$

Ниль де Бодрап
источник

поправьте меня, если я ошибаюсь: вы даете интуитивное объяснение, почему дерандомизация кажется невозможной, но мы знаем, что при некоторых разумных предположениях BPP, ZPP и P - это одно и то же. так что интуиция не обязательно будет полезна

Сашо Николов

Не за что. Дерандомизация, по-видимому, могла бы помочь понять, как моделировать BPP с помощью P , не так ли? Я просто описываю, как, если он хочет получить безусловные результаты, которые не используют структуру самого алгоритма, он может также выполнить детерминированное моделирование как рандомизированное с нулевой ошибкой. Или что-то не так с этим объяснением?

Ниль де Бодрап,

я думаю, все, что вы говорите, это то, что моделирование наивной грубой силы BPP с помощью ZPP не намного быстрее, чем моделирование наивной грубой силы BPP П., но я не могу увидеть, что это должно показать. для меня это похоже на то, как будто кто-то спрашивает: «Каков самый быстрый алгоритм для нахождения максимального соответствия» и получает в качестве ответа «ну, если не понять структуру соответствий, это экспоненциальное время». вопрос заключается в том, существует ли какое-либо известное понимание структуры BPP, которая делает возможным эффективное моделирование ZPP

Сашо Николов

@SashoNikolov: На самом деле это не было глубоким пониманием. Из формулировки вопроса мне показалось, что он граничит с переходом на CS.SE. Я решил ответить буквально на это, а именно: насколько нам известно , наиболее эффективное ожидаемое время работы машины Лас-Вегаса, которая принимает язык L∈BPP, не намного лучше, чем детерминированная машина, которая исследует возможности грубой силы. Ответы, в которых говорится, что это может быть некоторая верхняя граница полинома, если выполняются некоторые условия, превосходные и информативные, и я голосую за них; но я обращаюсь к актуальному вопросу.

Ниль де Бодрап

Я думаю, что это хороший ответ (также более читаемый теперь после редактирования). У нас нет условного результата, такого как «P = ZPP подразумевает P = BPP» или «ZPP = BPP подразумевает P = BPP», поэтому все еще возможно, что мы можем моделировать BPP с помощью алгоритмов ZP быстрее, чем с помощью детерминированных алгоритмов. Однако результат релятивизации, по-видимому, подразумевает, что это не может произойти при любом релятивизирующем моделировании, я правильно понимаю?

Каве