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

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

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

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

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

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

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

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

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

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

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

Probabilistically checkable proofs


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