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