Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/BPP in PSPACE — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
Celyh (обсуждение | вклад) |
||
| Строка 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> | ||
Версия 17:34, 12 декабря 2014
Докажите, что .
Не используя теорему Лаутемана (не палите из пушек по воробьям!). Просто посмотрите на определения обоих классов.