Теория сложности

Материал из Викиконспекты
Версия от 20:20, 4 июня 2012; 194.85.161.2 (обсуждение) (Отмена правки 23829 участника 194.85.161.2 (обсуждение))
Перейти к: навигация, поиск
Эта статья находится в разработке!

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

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

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

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

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

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

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

Probabilistically checkable proofs


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