Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/ex-zpp-notnull — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) (Массовая правка: добавление Категория:Теоретические задачи) |
||
| (не показано 19 промежуточных версий 2 участников) | |||
| Строка 1: | Строка 1: | ||
<latex>Класс сложности $ZPP_{NotNull}$ состоит из всех языков $L$, для которых существует ВМТ M, | <latex>Класс сложности $ZPP_{NotNull}$ состоит из всех языков $L$, для которых существует ВМТ M, | ||
всегда возвращающая правильные ответы (т.\,е. никаких «не знаю»), причем $\exists$ полином $p(n)$, что для времени работы $T_M(x)$ машины M выполняется: | всегда возвращающая правильные ответы (т.\,е. никаких «не знаю»), причем $\exists$ полином $p(n)$, что для времени работы $T_M(x)$ машины M выполняется: | ||
| − | \[ | + | \[ |
| − | + | \mathrm{E} T_M(x) \leq p(|x|). | |
\] | \] | ||
| − | Докажите, что $ZPP_{NotNull}=ZPP$. | + | Докажите, что $ZPP_{NotNull}=ZPP$. |
</latex> | </latex> | ||
| − | + | [[Категория:Решенные задачи]] | |
| − | [[ | + | [[Категория:Теоретические задачи]] |
| − | + | ||
Текущая версия на 06:50, 4 мая 2023