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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Вероятностные сложностные классы)
(Детерминированные и недетерминированные вычисления, сложность по времени и по памяти)
(не показано 27 промежуточных версий 13 участников)
Строка 1: Строка 1:
{{В разработке}}
 
 
 
[[Категория: Теория сложности]]
 
[[Категория: Теория сложности]]
  
 
== Детерминированные и недетерминированные вычисления, сложность по времени и по памяти ==
 
== Детерминированные и недетерминированные вычисления, сложность по времени и по памяти ==
*[[Сложностные классы. Вычисления с оракулом]]
+
=== Базовые определения ===
 +
*[[Сложностные классы]]
 +
*[[Вычисления с оракулом]]
  
 
=== Классы P и NP, NP-полнота ===
 
=== Классы P и NP, NP-полнота ===
 
*[[Класс P]]
 
*[[Класс P]]
 
*[[Недетерминированные вычисления]]
 
*[[Недетерминированные вычисления]]
*[[Классы NP и Σ₁]]
+
*[[Классы NP, coNP, Σ₁, Π₁]]
 
*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
 
*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
*[[Примеры NP-полных языков. Теорема Кука]]
+
*[[Сведение по Куку задачи факторизации к языку из NP]]
 +
*[[NP-полнота BH1N]]
 +
*[[Теорема Кука]]
 
*[[Теоремы о временной и емкостной иерархиях]]
 
*[[Теоремы о временной и емкостной иерархиях]]
 
*[[Теорема Бейкера — Гилла — Соловэя]]
 
*[[Теорема Бейкера — Гилла — Соловэя]]
Строка 19: Строка 21:
 
*[[Теорема Махэни]]
 
*[[Теорема Махэни]]
  
=== Сложность по памяти, классы PS, L, NL, coNL ===
+
=== [[Примеры NP-полных языков]] ===
 +
* [[NP-полнота языка CNFSAT]]
 +
* [[NP-полнота языка 3SAT]]
 +
* [[NP-полнота языка IND (максимальное независимое множество)]]
 +
* [[NP-полнота языка VCOVER (минимальное вершинное покрытие)]]
 +
* [[NP-полнота языка CLIQUE]]
 +
* [[NP-полнота задач о гамильтоновом цикле и пути в графах]]
 +
* [[NP-полнота задачи о сумме подмножества]]
 +
* [[NP-полнота задачи о рюкзаке]]
 +
* [[NP-полнота задачи о раскраске графа]]
 +
* [[NP-полнота игры Тетрис]]
 +
 
 +
=== Сложность по памяти, классы 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]]
*[[NL-полнота задачи о достижимости]]
+
*[[Полнота относительно L-сведения. NL-полнота. P-полнота]]
 
*[[Теорема Иммермана]]
 
*[[Теорема Иммермана]]
 +
*[[Классы EXP и NEXP]]
  
 
=== Полиномиальная иерархия ===
 
=== Полиномиальная иерархия ===
 
*[[Классы PH, Σ и Π]]
 
*[[Классы PH, Σ и Π]]
 
*[[Теоремы о коллапсе полиномиальной иерархии]]
 
*[[Теоремы о коллапсе полиномиальной иерархии]]
 +
 +
=== Классы задач подсчета ===
 +
*[[Классы Sharp P, Sharp P-Complete|Классы #P, #P-Complete]]
  
 
== Схемная сложность ==
 
== Схемная сложность ==
Строка 38: Строка 57:
  
 
== Вероятностные сложностные классы ==
 
== Вероятностные сложностные классы ==
 +
=== Основные классы ===
 
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
 
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
 
*[[Классы RP и coRP]]
 
*[[Классы RP и coRP]]
 
*[[Класс ZPP]]
 
*[[Класс ZPP]]
*[[Классы BPP, BPPweak и BPPstrong]]
+
*[[Классы BPP и PP]]
 +
*[[Соотношение вероятностных классов]]
 +
*[[Лемма Шварца-Зиппеля]]
 
*[[Теорема Лаутемана]]
 
*[[Теорема Лаутемана]]
 +
*[[Теорема Валианта-Вазирани]]
  
 
=== Интерактивные протоколы ===
 
=== Интерактивные протоколы ===
 
*[[Интерактивные протоколы. Класс IP. Класс AM]]
 
*[[Интерактивные протоколы. Класс IP. Класс AM]]
*[[Связь классов IP и AM друг с другом и с другими классами языков]]
 
 
*[[Арифметизация булевых формул с кванторами]]
 
*[[Арифметизация булевых формул с кванторами]]
*[[Лемма о соотношении coNP и IP]]
+
*[[Теорема о соотношении coNP и IP]]
 
*[[Теорема Шамира]]
 
*[[Теорема Шамира]]
 
*[[Семейство универсальных попарно независимых хеш-функций]]
 
*[[Семейство универсальных попарно независимых хеш-функций]]
*[[Протокол Голдвассера-Сипсера для оценки размера множества]]
+
*[[Протокол Голдвассер-Сипсера для оценки размера множества]]
  
 
=== Probabilistically checkable proofs ===
 
=== Probabilistically checkable proofs ===
 
*[[PCP-система]]
 
*[[PCP-система]]
 +
*[[Эквивалентность PCP-теоремы и теоремы о трудности аппроксимации]]
 
*[[PCP-теорема]]
 
*[[PCP-теорема]]
*[[PCP-теорема, альтернативное доказательство | PCP-теорема, альтернативная формулировка]]
 
  
 
----
 
----
  
 
[[Теория сложности (старая трешовая версия)|Вот сюда]] можно подсматривать, но злоупотреблять не рекомендуется.
 
[[Теория сложности (старая трешовая версия)|Вот сюда]] можно подсматривать, но злоупотреблять не рекомендуется.

Версия 10:50, 1 июня 2017


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

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

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

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

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

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

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

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

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

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

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

Probabilistically checkable proofs


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