Теория сложности — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Вероятностные сложностные классы)
м (Вероятностные сложностные классы)
Строка 41: Строка 41:
 
*[[Классы RP и coRP]]
 
*[[Классы RP и coRP]]
 
*[[Класс ZPP]]
 
*[[Класс ZPP]]
*[[Класс BPP]]
+
*[[Класс BPP и PP]]
 
*[[Соотношение вероятностных классов]]
 
*[[Соотношение вероятностных классов]]
 
*[[Теорема Лаутемана]]
 
*[[Теорема Лаутемана]]

Версия 23:50, 4 июня 2012

Эта статья находится в разработке!

Детерминированные и недетерминированные вычисления, сложность по времени и по памяти

Классы P и NP, NP-полнота

Сложность по памяти, классы PS, L, NL, coNL

Полиномиальная иерархия

Схемная сложность

Вероятностные сложностные классы

Интерактивные протоколы

Probabilistically checkable proofs


Вот сюда можно подсматривать, но злоупотреблять не рекомендуется.