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

Материал из Викиконспекты
Версия от 23:29, 6 марта 2016; Shersh (обсуждение | вклад) (Примеры NP-полных языков: добавлен конспект про тетрис)
Перейти к: навигация, поиск


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

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

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

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

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

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

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

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