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

Материал из Викиконспекты
Перейти к: навигация, поиск


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

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

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

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

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

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

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

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

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

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

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

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


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