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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Интерактивные протоколы)
Строка 1: Строка 1:
{{В разработке}}
 
 
 
[[Категория: Теория сложности]]
 
[[Категория: Теория сложности]]
  

Версия 18:48, 16 апреля 2014


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

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

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

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

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

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

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

Probabilistically checkable proofs



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