11
правок
Изменения
Нет описания правки
В приведенных определениях <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_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>
Доказательство проводится аналогично приведенному в первой части. Запустим машину <tex>m</tex> из <tex>RP</tex> <tex>k</tex> раз. С учетом ограничения, введенного в определении класса <tex>RP_2</tex>, получим неравенство: <tex>(\frac{1}{2})^k < \frac{1}{2^{p(n)}}</tex>.
Прологарифмировав и сократив обе части неравенства на <tex>ln(\frac{1}{2})</tex>, получим неравенство: <tex>k > p(n)</tex>. То есть машина <tex>m</tex>, запущенная <tex>k</tex> раз, выдает неверный ответ с вероятностью, удовлетворяющей определению класса <tex>RP_2</tex>, а значит <tex>RP \subset RP_2</tex>.
Эквивалентность определений класса <tex>RP</tex> доказана.
