Теория сложности — различия между версиями
Shersh (обсуждение | вклад) (→3. Примеры NP-полных языков) |
Shersh (обсуждение | вклад) (→Сложность по памяти, классы PS, L, NL, coNL: раздел обновлён) |
||
| Строка 32: | Строка 32: | ||
* [[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]] | ||
=== Полиномиальная иерархия === | === Полиномиальная иерархия === | ||
Версия 21:02, 5 марта 2016
Содержание
Детерминированные и недетерминированные вычисления, сложность по времени и по памяти
Базовые определения
Классы P и NP, NP-полнота
- Класс P
- Недетерминированные вычисления
- Классы NP и Σ₁
- Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
- NP-полнота BH1N
- Теорема Кука
- Теоремы о временной и емкостной иерархиях
- Теорема Бейкера — Гилла — Соловэя
- Теорема Ладнера
- Теорема Левина
- Теорема Бермана — Форчуна
- Теорема Махэни
Примеры NP-полных языков
- NP-полнота языка CNFSAT
- NP-полнота языка 3SAT
- NP-полнота языка IND (максимальное независимое множество)
- NP-полнота языка VCOVER (минимальное вершинное покрытие)
- NP-полнота языка FACTOR
- NP-полнота языка CLIQUE
- 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
Полиномиальная иерархия
Схемная сложность
- Схемная сложность и класс P/poly
- Теорема Карпа — Липтона
- Классы NC и AC
- Теорема о непринадлежности XOR классу AC⁰
Вероятностные сложностные классы
Основные классы
- Вероятностные вычисления. Вероятностная машина Тьюринга
- Классы RP и coRP
- Класс ZPP
- Классы BPP и PP
- Соотношение вероятностных классов
- Теорема Лаутемана
Интерактивные протоколы
- Интерактивные протоколы. Класс IP. Класс AM
- Арифметизация булевых формул с кванторами
- Теорема о соотношении coNP и IP
- Теорема Шамира
- Семейство универсальных попарно независимых хеш-функций
- Протокол Голдвассер-Сипсера для оценки размера множества
Probabilistically checkable proofs
Вот сюда можно подсматривать, но злоупотреблять не рекомендуется.
