Изменения

Перейти к: навигация, поиск

Теорема Голдвассера, Сипсера

5 байт добавлено, 15:04, 20 мая 2010

→‎Доказательство

==Доказательство==

Заметим что, очевидно, <tex>AM[f(n)+O(1)] \subset IP[f(n)], \forall f</tex>.

Докажем теперь, что <tex>IP \subset AM</tex>

Анонимный участник

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/1163»