1632
правки
Изменения
м
rollbackEdits.php mass rollback
==Определение классов <tex>PRRP, RP_1, RP_2</tex>==
Множество языков [[Сложностные_классы_RP_и_coRP |'''RP''']] определяется следующим образом:
==Доказательство эквивалентности определений==
Включение <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>
