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

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

Текущая версия на 19:42, 4 сентября 2022


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

Базовые определения

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

Примеры NP-полных языков

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

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

Классы задач подсчета

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

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

Основные классы

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

Probabilistically checkable proofs


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