|
|
Строка 4: |
Строка 4: |
| Просто посмотрите на определения обоих классов. | | Просто посмотрите на определения обоих классов. |
| | | |
− | [[Category:На проверку]] | + | [[Category:Решенные задачи]] |
| <!--Вообще-то, решения уже есть--> | | <!--Вообще-то, решения уже есть--> |
− | <latex>
| |
− | Решение (Целых Влады, 974):
| |
− | Пусть $M$---вероятностная машина Тьюринга, распознающая язык $L\in BPP$. Тогда
| |
− | из определения класса сложности $BPP$ следует, что
| |
− | \begin{align*}
| |
− | & x\in L \Rightarrow P(M(x)=1) \geq \frac{2}{3}\\
| |
− | & x \not \in L \Rightarrow P(M(x)=0) \geq \frac{2}{3}
| |
− | \end{align*}
| |
− |
| |
− | Пусть на входе $x$ ВМТ делает $q(|x|)$ случайных шагов, причем на каждом из случайных шагов происходит
| |
− | выбор из $2$ вариантов. Тогда всего $2^{q(|x|)}$ равновероятных возможных исходов. Построим детерминированную
| |
− | МТ $M_2$, которая перебирает возможные исходы и считает долю исходов, на которых $x$ принимается $M$.
| |
− | Если доля больше $2/3$, то выдается ответ $x\in L$, иначе $x\not \in L$. При работе $M_2$ после вычисления
| |
− | ответа $M$ на определенном исходе, память переиспользуется (т.к. нужно помнить лишь число исходов, на которых $x$
| |
− | принимается). Т.о. требуется полиномиальное
| |
− | количество памяти.
| |
− |
| |
− | <\latex>
| |
Версия 10:35, 24 декабря 2014
Докажите, что .
Не используя теорему Лаутемана (не палите из пушек по воробьям!).
Просто посмотрите на определения обоих классов.