Уменьшение ошибки в классе RP, сильное и слабое определение

Определение классов [math]RP, RP_1, RP_2[/math]

Множество языков RP определяется следующим образом:

[math]RP = \{L \mid \exists m: P(m(x) = 1 \mid x \in L) \geq \frac{1}{2}, P(m(x) = 0 \mid x \notin L) = 1\}[/math]

Определим множества языков [math]RP_1[/math] и [math]RP_2[/math]:

[math]RP_1 = \{L \mid \exists m: P(m(x) = 1 \mid x \in L) \geq \frac{1}{p(|x|)}, P(m(x) = 0 \mid x \notin L) = 1\}[/math]

[math]RP_2 = \{L \mid \exists m: P(m(x) = 1 \mid x \in L) \geq 1 - \frac{1}{2^{p(|x|)}}, P(m(x) = 0 \mid x \notin L) = 1\}[/math]

В приведенных определениях [math]p(|x|)[/math] — некий полином, а [math]m[/math] — вероятностная машина Тьюринга, время работы которой в худшем случае составляет полином от длины входа.

В классе [math]RP_1[/math] ослаблено ограничение на вероятность ошибки ответа, а в классе [math]RP_2[/math] усилено. Соответственно [math]RP_1[/math] называется слабым определением класса [math]RP[/math], а [math]RP_2[/math] — сильным.

Доказательство эквивалентности определений

Включение [math]RP_2 \subset RP \subset RP_1[/math] очевидно, следовательно осталось доказать обратное включение [math]RP_1 \subset RP \subset RP_2[/math]. Доказательство данного утверждения проводится с помощью метода уменьшения ошибки в классе [math]RP[/math].

• Докажем включение [math]RP_1 \subset RP[/math]

Выясним, сколько раз требуется запустить машину Тьюринга [math]m[/math] из [math]RP_1[/math], для того, чтобы вероятность ошибки была меньше [math]\frac{1}{2}[/math]. Запустим машину [math]m[/math] [math]k[/math] раз, тогда вероятность ошибки составит [math](1 - \frac{1}{p(n)})^k[/math]. Получим неравенство: [math](1 - \frac{1}{p(n)})^k \lt \frac{1}{2}[/math]

Логарифмируя, сведем к следующему: [math]k\ ln(1 - \frac{1}{p(n)}) \lt ln(\frac{1}{2})[/math]

Разложив логарифм в левой части в ряд, получим: [math]k(-\frac{1}{p(n)} + o(\frac{1}{p(n)})) \lt ln(\frac{1}{2})[/math]

Откуда [math]k \gt p(n)ln(2)[/math], где [math]n[/math] — длина входа. То есть при [math]k[/math], удовлетворяющем полученному неравенству, вероятность ошибки не будет превышать [math]\frac{1}{2}[/math], а значит [math]RP_1 \subset RP[/math].

• Докажем включение [math]RP \subset RP_2[/math]

Доказательство проводится аналогично приведенному в первой части. Запустим машину [math]m[/math] из [math]RP[/math] [math]k[/math] раз. С учетом ограничения, введенного в определении класса [math]RP_2[/math], получим неравенство: [math](\frac{1}{2})^k \lt \frac{1}{2^{p(n)}}[/math].

Прологарифмировав и сократив обе части неравенства на [math]ln(\frac{1}{2})[/math], получим неравенство: [math]k \gt p(n)[/math]. То есть машина [math]m[/math], запущенная [math]k[/math] раз, выдает неверный ответ с вероятностью, удовлетворяющей определению класса [math]RP_2[/math], а значит [math]RP \subset RP_2[/math].

Эквивалентность определений класса [math]RP[/math] доказана.