Теория сложности

Материал из Викиконспекты
Версия от 10:50, 1 июня 2017; 176.59.10.248 (обсуждение) (Детерминированные и недетерминированные вычисления, сложность по времени и по памяти)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск


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

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

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

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

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

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

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

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

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

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

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

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


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