Изменения
Нет описания правки
*[[Классы NC и AC]]
*[[Теорема о не принадлежности XOR классу AC⁰]]
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
*[[Теоремы о BPP, BPPweak и BPPstrong]]
*[[Уменьшение ошибки в классе RP]]
*[[Теорема Лаутемана]]
*[[Интерактивные протоколы. Класс IP. Класс AM]]
*[[Связь классов IP и AM друг с другом и с другими классами языков]]
*[[Лемма о соотношении coNP и IP]]
*[[Теорема Шамира]]
*[[Семейство универсальных попарно независимых хеш-функций]]
*[[Протокол Голдвассера-Сипсера для оценки размера множества]]
----
[[Теория сложности (старая трешовая версия)|Вот сюда]] можно подсматривать, но злоупотреблять не рекомендуется.
