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

Материал из Викиконспекты
Перейти к: навигация, поиск
(переименовал Теория сложности в Теория сложности (старая трешовая версия): Мы создаём свой конспект. Хороший, красивый и ясный.)
 
(Детерминированные и недетерминированные вычисления, сложность по времени и по памяти)
 
(не показаны 52 промежуточные версии 23 участников)
Строка 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-теорема]]
 +
 
 +
----
 +
 
 +
[[Теория сложности (старая трешовая версия)|Вот сюда]] можно подсматривать, но злоупотреблять не рекомендуется.

Текущая версия на 10:50, 1 июня 2017


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

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

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

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

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

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

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

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

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

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

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

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


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