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

Материал из Викиконспекты
Версия от 22:50, 24 февраля 2016; Shersh (обсуждение | вклад) (Детерминированные и недетерминированные вычисления, сложность по времени и по памяти)
Перейти к: навигация, поиск


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

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

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

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

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

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

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

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

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

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

Probabilistically checkable proofs



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