11
правок
Изменения
Новая страница: «==Определение классов <tex>PR, RP_1, RP_2</tex>== Множество языков '''RP''' оп…»
==Определение классов <tex>PR, RP_1, RP_2</tex>==
Множество языков [[Сложностные_классы_RP_и_coRP |'''RP''']] определяется следующим образом:
<tex>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\}</tex>
Определим множества языков <tex>RP_1</tex> и <tex>RP_2</tex>:
<tex>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\}</tex>
<tex>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\}</tex>
В приведенных определениях <tex>p(|x|)</tex> — некий полином, а <tex>m</tex> — [[Вероятностные машины Тьюринга | вероятностная машина Тьюринга]], время работы которой в худшем случае составляет полином от длины входа.
В классе <tex>RP_1</tex> ослаблено ограничение на вероятность ошибки ответа, а в классе <tex>RP_2</tex> усилено. Соответственно <tex>RP_1</tex> называется слабое определением класса <tex>RP</tex>, а <tex>RP_2</tex> — сильным.
==Доказательство эквивалентности определений==
Включение <tex>RP_2 \subset RP \subset RP_1</tex> очевидно, следовательно осталось доказать обратное включение: <tex>RP_1 \subset RP \subset RP_2</tex>. Доказательство данного утверждения проводится с помощью метода уменьшения ошибки в классе <tex>RP</tex>.
* Докажем включение <tex>RP_1 \subset RP</tex>
Выясним, сколько раз требуется запустить машину Тьюринга <tex>m</tex> из <tex>RP_1</tex>, для того, чтобы вероятность ошибки была меньше <tex>\frac{1}{2}</tex>. Запустим машину <tex>m</tex> <tex>k</tex> раз, тогда вероятность ошибки составит <tex>(1 - \frac{1}{p(n)})^k</tex>. Получим неравенство:
<tex>(1 - \frac{1}{p(n)})^k < \frac{1}{2}</tex>
Логарифмируя, сведем к следующему: <tex>k\ ln(1 - \frac{1}{p(n)}) < ln(\frac{1}{2})</tex>
Разложив логарифм в левой части в ряд, получим: <tex>k(-\frac{1}{p(n)} + o(\frac{1}{p(n)})) < ln(\frac{1}{2})</tex>
Откуда <tex>k > p(n)ln(2)</tex>, где <tex>n</tex> — длина входа. То есть при <tex>k</tex>, удовлетворяющем полученному неравенству вероятность ошибки не будет превышать <tex>\frac{1}{2}</tex>, а следовательно <tex>RP_1 \subset RP</tex>.
* Докажем включение <tex>RP \subset RP_2</tex>
Множество языков [[Сложностные_классы_RP_и_coRP |'''RP''']] определяется следующим образом:
<tex>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\}</tex>
Определим множества языков <tex>RP_1</tex> и <tex>RP_2</tex>:
<tex>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\}</tex>
<tex>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\}</tex>
В приведенных определениях <tex>p(|x|)</tex> — некий полином, а <tex>m</tex> — [[Вероятностные машины Тьюринга | вероятностная машина Тьюринга]], время работы которой в худшем случае составляет полином от длины входа.
В классе <tex>RP_1</tex> ослаблено ограничение на вероятность ошибки ответа, а в классе <tex>RP_2</tex> усилено. Соответственно <tex>RP_1</tex> называется слабое определением класса <tex>RP</tex>, а <tex>RP_2</tex> — сильным.
==Доказательство эквивалентности определений==
Включение <tex>RP_2 \subset RP \subset RP_1</tex> очевидно, следовательно осталось доказать обратное включение: <tex>RP_1 \subset RP \subset RP_2</tex>. Доказательство данного утверждения проводится с помощью метода уменьшения ошибки в классе <tex>RP</tex>.
* Докажем включение <tex>RP_1 \subset RP</tex>
Выясним, сколько раз требуется запустить машину Тьюринга <tex>m</tex> из <tex>RP_1</tex>, для того, чтобы вероятность ошибки была меньше <tex>\frac{1}{2}</tex>. Запустим машину <tex>m</tex> <tex>k</tex> раз, тогда вероятность ошибки составит <tex>(1 - \frac{1}{p(n)})^k</tex>. Получим неравенство:
<tex>(1 - \frac{1}{p(n)})^k < \frac{1}{2}</tex>
Логарифмируя, сведем к следующему: <tex>k\ ln(1 - \frac{1}{p(n)}) < ln(\frac{1}{2})</tex>
Разложив логарифм в левой части в ряд, получим: <tex>k(-\frac{1}{p(n)} + o(\frac{1}{p(n)})) < ln(\frac{1}{2})</tex>
Откуда <tex>k > p(n)ln(2)</tex>, где <tex>n</tex> — длина входа. То есть при <tex>k</tex>, удовлетворяющем полученному неравенству вероятность ошибки не будет превышать <tex>\frac{1}{2}</tex>, а следовательно <tex>RP_1 \subset RP</tex>.
* Докажем включение <tex>RP \subset RP_2</tex>
