Классы BPP

Материал из Викиконспекты
Версия от 12:28, 1 июня 2012; 93.100.30.106 (обсуждение) (Новая страница: «==Определения== {{Определение |definition= <tex>BPP_{weak}</tex> — множество языков <tex>L</tex>, для которых с...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Определения

Определение:
[math]BPP_{weak}[/math] — множество языков [math]L[/math], для которых существует [math]p[/math], такая, что для любого [math]x[/math]:
  1. [math]P(p(x)=[x \in L]) \ge \frac {1}{2} + \frac {1} {q(|x|)}[/math], где [math]q[/math]-полином;
  2. [math]T(p(x)) \le poly(|x|)[/math] для любой вероятностной ленты.


Определение:
[math]BPP_{strong}[/math] — множество языков [math]L[/math], для которых существует [math]p[/math], такая, что для любого [math]x[/math]:
  1. [math]P(p(x)=[x \in L]) \ge 1 - 1 / {2^{q(|x|)}}[/math], где [math]q[/math]-полином;
  2. [math]T(p(x)) \le poly(|x|)[/math] для любой вероятностной ленты.
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Классы_BPP&oldid=23122»