Теория сложности — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Примеры NP-полных языков)
(Классы P и NP, NP-полнота)
Строка 11: Строка 11:
 
*[[Классы NP, coNP, Σ₁, Π₁]]
 
*[[Классы NP, coNP, Σ₁, Π₁]]
 
*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
 
*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
 +
*[[Сведение по Куку задачи факторизации к языку из NP]]
 
*[[NP-полнота BH1N]]
 
*[[NP-полнота BH1N]]
 
*[[Теорема Кука]]
 
*[[Теорема Кука]]

Версия 20:07, 22 июня 2016


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

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

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

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

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

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

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

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

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

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

Probabilistically checkable proofs


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