Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/amplify-when-specific-error-bounded — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) (Массовая правка: добавление Категория:Теоретические задачи) |
||
| (не показано 6 промежуточных версий этого же участника) | |||
| Строка 15: | Строка 15: | ||
[[Категория:Решенные задачи]] | [[Категория:Решенные задачи]] | ||
| + | [[Категория:Теоретические задачи]] | ||
Текущая версия на 06:50, 4 мая 2023
Пусть A — вероятностный алгоритм, вычисляющий f(x).
Но не очень полезный:
- Prob(A(x)=f(x)) >= ⅓
Правда известен факт, что для любого неверного результата w
- Prob(A(x)=w) <= ¼
Можно ли как-то из A сделать полезный алгоритм?