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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Сложность по памяти, классы PS, L, NL, coNL)
Строка 27: Строка 27:
 
*[[PS-полнота языка верных булевых формул с кванторами (TQBF)]]
 
*[[PS-полнота языка верных булевых формул с кванторами (TQBF)]]
 
*[[Классы L, NL, coNL]]
 
*[[Классы L, NL, coNL]]
*[[NL-полнота задачи о достижимости]]
+
*[[Полнота относительно L-сведения. NL-полнота. P-полнота]]
 
*[[Теорема Иммермана]]
 
*[[Теорема Иммермана]]
  

Версия 16:39, 14 марта 2013

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

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

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

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

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

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

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

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

Probabilistically checkable proofs



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