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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Дополнительные классы)
(Детерминированные и недетерминированные вычисления, сложность по времени и по памяти)
 
Строка 47: Строка 47:
 
*[[Теоремы о коллапсе полиномиальной иерархии]]
 
*[[Теоремы о коллапсе полиномиальной иерархии]]
  
=== Дополнительные классы ===
+
=== Классы задач подсчета ===
 
*[[Классы Sharp P, Sharp P-Complete|Классы #P, #P-Complete]]
 
*[[Классы Sharp P, Sharp P-Complete|Классы #P, #P-Complete]]
  

Текущая версия на 10:50, 1 июня 2017


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

Базовые определения[править]

Классы P и NP, NP-полнота[править]

Примеры NP-полных языков[править]

Сложность по памяти, классы PS, L, NL, coNL, EXP, NEXP[править]

Полиномиальная иерархия[править]

Классы задач подсчета[править]

Схемная сложность[править]

Вероятностные сложностные классы[править]

Основные классы[править]

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

Probabilistically checkable proofs[править]


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