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