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

Материал из Викиконспекты
Перейти к: навигация, поиск
(3. Примеры NP-полных языков)
м (rollbackEdits.php mass rollback)
 
(не показано 11 промежуточных версий 6 участников)
Строка 9: Строка 9:
 
*[[Класс P]]
 
*[[Класс P]]
 
*[[Недетерминированные вычисления]]
 
*[[Недетерминированные вычисления]]
*[[Классы NP и Σ₁]]
+
*[[Классы 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-полнота задач о гамильтоновом цикле и пути в графах]]
Строка 31: Строка 31:
 
* [[NP-полнота задачи о рюкзаке]]
 
* [[NP-полнота задачи о рюкзаке]]
 
* [[NP-полнота задачи о раскраске графа]]
 
* [[NP-полнота задачи о раскраске графа]]
 +
* [[NP-полнота игры Тетрис]]
  
=== Сложность по памяти, классы PS, L, NL, coNL ===
+
=== Сложность по памяти, классы PS, L, NL, coNL, EXP, NEXP ===
 
*[[Класс PS. Связь класса PS с другими классами теории сложности]]
 
*[[Класс PS. Связь класса PS с другими классами теории сложности]]
 
*[[Теорема Сэвича. Совпадение классов NPS и PS]]
 
*[[Теорема Сэвича. Совпадение классов NPS и PS]]
 
*[[PS-полнота языка верных булевых формул с кванторами (TQBF)]]
 
*[[PS-полнота языка верных булевых формул с кванторами (TQBF)]]
 +
*[[PS-полнота задачи Generalized geography]]
 
*[[Классы L, NL, coNL]]
 
*[[Классы L, NL, coNL]]
 
*[[Полнота относительно L-сведения. NL-полнота. P-полнота]]
 
*[[Полнота относительно L-сведения. NL-полнота. P-полнота]]
 
*[[Теорема Иммермана]]
 
*[[Теорема Иммермана]]
 +
*[[Классы EXP и NEXP]]
  
 
=== Полиномиальная иерархия ===
 
=== Полиномиальная иерархия ===
 
*[[Классы PH, Σ и Π]]
 
*[[Классы PH, Σ и Π]]
 
*[[Теоремы о коллапсе полиномиальной иерархии]]
 
*[[Теоремы о коллапсе полиномиальной иерархии]]
 +
 +
=== Классы задач подсчета ===
 +
*[[Классы Sharp P, Sharp P-Complete|Классы #P, #P-Complete]]
  
 
== Схемная сложность ==
 
== Схемная сложность ==
Строка 57: Строка 63:
 
*[[Классы BPP и PP]]
 
*[[Классы BPP и PP]]
 
*[[Соотношение вероятностных классов]]
 
*[[Соотношение вероятностных классов]]
 +
*[[Лемма Шварца-Зиппеля]]
 
*[[Теорема Лаутемана]]
 
*[[Теорема Лаутемана]]
 +
*[[Теорема Валианта-Вазирани]]
  
 
=== Интерактивные протоколы ===
 
=== Интерактивные протоколы ===
Строка 71: Строка 79:
 
*[[Эквивалентность PCP-теоремы и теоремы о трудности аппроксимации]]
 
*[[Эквивалентность PCP-теоремы и теоремы о трудности аппроксимации]]
 
*[[PCP-теорема]]
 
*[[PCP-теорема]]
 
  
 
----
 
----
  
 
[[Теория сложности (старая трешовая версия)|Вот сюда]] можно подсматривать, но злоупотреблять не рекомендуется.
 
[[Теория сложности (старая трешовая версия)|Вот сюда]] можно подсматривать, но злоупотреблять не рекомендуется.

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


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

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

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

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

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

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

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

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

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

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

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

Probabilistically checkable proofs


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