Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/RP in PPoly — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
Bunakov (обсуждение | вклад) |
||
Строка 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
Докажите, что .