Изменения

Вероятностные вычисления. Вероятностная машина Тьюринга

36 байт убрано, 13:26, 31 мая 2012

→‎Соотношение вероятностных классов

{{Теорема

|statement =

# <tex>\mathrm{RP} \~~subset \mathrm{BPP}</tex>;<br># <tex>~~cup \mathrm{coRP} \subset \mathrm{BPP}</tex>.

|proof =

Пусть <tex>p</tex> — программа для <tex>L \in RP</tex>. Программу <tex>q</tex> для <tex>\mathrm{BPP}</tex> определим следующим образом:

322

правки