Вероятностные вычисления. Классы 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
Докажите, что .
Не используя теорему Лаутемана (не палите из пушек по воробьям!). Просто посмотрите на определения обоих классов.