Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/RP in PPoly — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
Докажите, что <m>RP \subseteq P/poly </m>.
 
Докажите, что <m>RP \subseteq P/poly </m>.
  
[[Category:Нерешенные задачи]]
+
[[Category:На проверку]]
 
<!--Вообще-то, решения уже есть-->
 
<!--Вообще-то, решения уже есть-->
 +
 +
<latex>
 +
 +
Решение (Василий Бунаков, 974 гр.)
 +
\smallskip
 +
 +
1. Известно, что $RP\subseteq BPP$ (следует непосредственно из определений). Покажем, что $BPP\subseteq P/Poly$.
 +
 +
2. Пусть $L\in BPP$ и $M$---полиномиальная МТ из определения класса BPP:
 +
\begin{align*}
 +
& x\in L \Rightarrow \text{ доля } y: M(x, y)=1 \geq \frac{2}{3}\\
 +
& x \not\in L \Rightarrow \text{ доля } y: M(x, y)=0\geq \frac{2}{3},
 +
\end{align*}
 +
где $|y|\leq p(|x|)$.
 +
 +
Построим допускающую язык $L$ полиномиальную МТ $T$ и полиномиальную подсказку $z$, зависящую только от длины входа (тем самым, доказав, что $L\in P/Poly$).
 +
Запустим машину $M$ $t = 18 |x|$ раз с разными значениями $y$ (эти $18 |x|$ значений $y$ и будут составлять подсказку $z$).
 +
Решение принимается на основе большинства результатов. Покажем, что существует такой набор из $18 |x|$ значений $y$ (подсказка),
 +
что принимаемое решение окажется верным для любого входа длины $|x|$.
 +
 +
Из оценки Чебышева вероятность верного ответа на конкретном входе $x$ оценивается как:
 +
$$
 +
P_{true} \geq 1 - \exp \left(-2 \left(\frac{2}{3}-\frac{1}{2}\right)^2 t\right) = 1 - \exp (-|x|)
 +
$$
 +
Отсюда вероятность неверного ответа (или, другими словами, доля подсказок $z$ длины $18 |x|$, приводящих к неверному результату):
 +
$$
 +
P_{false} \leq \exp (-|x|)
 +
$$
 +
 +
Т.к. всего $2^{|x|}$ возможных входов длины $|x|$, то доля подсказок, приводящих к неверному
 +
результату хотя бы для одного входа длины $|x|$ не превосходит:
 +
$$
 +
\frac{2^{|x|}}{\exp(|x|)} < 1
 +
$$
 +
Значит, существуют полиномиальные подсказки, приводящие к верному результату для любого входа длины $|x|$, что и требовалось доказать.
 +
 +
 +
</latex>

Версия 21:07, 25 декабря 2014

Докажите, что .