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

Материал из Викиконспекты
Перейти к: навигация, поиск
(переименовал Теория сложности в Теория сложности (старая трешовая версия): Мы создаём свой конспект. Хороший, красивый и ясный.)
 
м (rollbackEdits.php mass rollback)
 
(не показаны 54 промежуточные версии 25 участников)
Строка 1: Строка 1:
#перенаправление [[Теория сложности (старая трешовая версия)]]
+
[[Категория: Теория сложности]]
 +
 
 +
== Детерминированные и недетерминированные вычисления, сложность по времени и по памяти ==
 +
=== Базовые определения ===
 +
*[[Сложностные классы]]
 +
*[[Вычисления с оракулом]]
 +
 
 +
=== Классы P и NP, NP-полнота ===
 +
*[[Класс P]]
 +
*[[Недетерминированные вычисления]]
 +
*[[Классы NP, coNP, Σ₁, Π₁]]
 +
*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
 +
*[[Сведение по Куку задачи факторизации к языку из NP]]
 +
*[[NP-полнота BH1N]]
 +
*[[Теорема Кука]]
 +
*[[Теоремы о временной и емкостной иерархиях]]
 +
*[[Теорема Бейкера — Гилла — Соловэя]]
 +
*[[Теорема Ладнера]]
 +
*[[Теорема Левина]]
 +
*[[Теорема Бермана — Форчуна]]
 +
*[[Теорема Махэни]]
 +
 
 +
=== [[Примеры NP-полных языков]] ===
 +
* [[NP-полнота языка CNFSAT]]
 +
* [[NP-полнота языка 3SAT]]
 +
* [[NP-полнота языка IND (максимальное независимое множество)]]
 +
* [[NP-полнота языка VCOVER (минимальное вершинное покрытие)]]
 +
* [[NP-полнота языка CLIQUE]]
 +
* [[NP-полнота задач о гамильтоновом цикле и пути в графах]]
 +
* [[NP-полнота задачи о сумме подмножества]]
 +
* [[NP-полнота задачи о рюкзаке]]
 +
* [[NP-полнота задачи о раскраске графа]]
 +
* [[NP-полнота игры Тетрис]]
 +
 
 +
=== Сложность по памяти, классы PS, L, NL, coNL, EXP, NEXP ===
 +
*[[Класс PS. Связь класса PS с другими классами теории сложности]]
 +
*[[Теорема Сэвича. Совпадение классов NPS и PS]]
 +
*[[PS-полнота языка верных булевых формул с кванторами (TQBF)]]
 +
*[[PS-полнота задачи Generalized geography]]
 +
*[[Классы L, NL, coNL]]
 +
*[[Полнота относительно L-сведения. NL-полнота. P-полнота]]
 +
*[[Теорема Иммермана]]
 +
*[[Классы EXP и NEXP]]
 +
 
 +
=== Полиномиальная иерархия ===
 +
*[[Классы PH, Σ и Π]]
 +
*[[Теоремы о коллапсе полиномиальной иерархии]]
 +
 
 +
=== Классы задач подсчета ===
 +
*[[Классы Sharp P, Sharp P-Complete|Классы #P, #P-Complete]]
 +
 
 +
== Схемная сложность ==
 +
*[[Схемная сложность и класс P/poly]]
 +
*[[Теорема Карпа — Липтона]]
 +
*[[Классы NC и AC]]
 +
*[[Теорема о непринадлежности XOR классу AC⁰]]
 +
 
 +
== Вероятностные сложностные классы ==
 +
=== Основные классы ===
 +
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
 +
*[[Классы RP и coRP]]
 +
*[[Класс ZPP]]
 +
*[[Классы BPP и PP]]
 +
*[[Соотношение вероятностных классов]]
 +
*[[Лемма Шварца-Зиппеля]]
 +
*[[Теорема Лаутемана]]
 +
*[[Теорема Валианта-Вазирани]]
 +
 
 +
=== Интерактивные протоколы ===
 +
*[[Интерактивные протоколы. Класс IP. Класс AM]]
 +
*[[Арифметизация булевых формул с кванторами]]
 +
*[[Теорема о соотношении coNP и IP]]
 +
*[[Теорема Шамира]]
 +
*[[Семейство универсальных попарно независимых хеш-функций]]
 +
*[[Протокол Голдвассер-Сипсера для оценки размера множества]]
 +
 
 +
=== Probabilistically checkable proofs ===
 +
*[[PCP-система]]
 +
*[[Эквивалентность PCP-теоремы и теоремы о трудности аппроксимации]]
 +
*[[PCP-теорема]]
 +
 
 +
----
 +
 
 +
[[Теория сложности (старая трешовая версия)|Вот сюда]] можно подсматривать, но злоупотреблять не рекомендуется.

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


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

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

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

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

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

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

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

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

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

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

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

Probabilistically checkable proofs


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