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

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


Содержание

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

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

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

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

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

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

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

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

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

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

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

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


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

Личные инструменты
Пространства имён
Варианты
Действия
Навигация
Инструменты