Изменения

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

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

458 байт убрано, 12:19, 18 мая 2010
План доказательства
==Формулировка теоремы==
<tex>IP[f(n)] = AM[f(n)+2]</tex>
 
==План доказательства==
Рассмотрим множество вероятностных лент <tex>R</tex> и его подмножество <tex>S \subset R</tex> - множество лент, на которых осуществляется допуск. Если для некоторого множества <tex>S</tex> и числа <tex>k</tex> выполняется <tex>|S| > 2K</tex>, то допустим слово.
==Доказательство==
Анонимный участник

Навигация