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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Классы P и NP, NP-полнота: переименован конспект)
м (rollbackEdits.php mass rollback)
 
(не показано 7 промежуточных версий 6 участников)
Строка 11: Строка 11:
 
*[[Классы NP, coNP, Σ₁, Π₁]]
 
*[[Классы NP, coNP, Σ₁, Π₁]]
 
*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
 
*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
 +
*[[Сведение по Куку задачи факторизации к языку из NP]]
 
*[[NP-полнота BH1N]]
 
*[[NP-полнота BH1N]]
 
*[[Теорема Кука]]
 
*[[Теорема Кука]]
Строка 25: Строка 26:
 
* [[NP-полнота языка IND (максимальное независимое множество)]]
 
* [[NP-полнота языка IND (максимальное независимое множество)]]
 
* [[NP-полнота языка VCOVER (минимальное вершинное покрытие)]]
 
* [[NP-полнота языка VCOVER (минимальное вершинное покрытие)]]
* [[NP-полнота языка FACTOR]]
 
 
* [[NP-полнота языка CLIQUE]]
 
* [[NP-полнота языка CLIQUE]]
 
* [[NP-полнота задач о гамильтоновом цикле и пути в графах]]
 
* [[NP-полнота задач о гамильтоновом цикле и пути в графах]]
Строка 46: Строка 46:
 
*[[Классы PH, Σ и Π]]
 
*[[Классы PH, Σ и Π]]
 
*[[Теоремы о коллапсе полиномиальной иерархии]]
 
*[[Теоремы о коллапсе полиномиальной иерархии]]
 +
 +
=== Классы задач подсчета ===
 +
*[[Классы Sharp P, Sharp P-Complete|Классы #P, #P-Complete]]
  
 
== Схемная сложность ==
 
== Схемная сложность ==
Строка 76: Строка 79:
 
*[[Эквивалентность PCP-теоремы и теоремы о трудности аппроксимации]]
 
*[[Эквивалентность PCP-теоремы и теоремы о трудности аппроксимации]]
 
*[[PCP-теорема]]
 
*[[PCP-теорема]]
 
  
 
----
 
----
  
 
[[Теория сложности (старая трешовая версия)|Вот сюда]] можно подсматривать, но злоупотреблять не рекомендуется.
 
[[Теория сложности (старая трешовая версия)|Вот сюда]] можно подсматривать, но злоупотреблять не рекомендуется.

Текущая версия на 19:42, 4 сентября 2022


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

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

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

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

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

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

Классы задач подсчета

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

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

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

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

Probabilistically checkable proofs


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