|
|
| Строка 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>
| |