Теория сложности — различия между версиями
Kirillova (обсуждение | вклад) (→Сложность по памяти, классы PS, L, NL, coNL) |
м (rollbackEdits.php mass rollback) |
||
| (не показаны 33 промежуточные версии 15 участников) | |||
| Строка 1: | Строка 1: | ||
| − | |||
| − | |||
[[Категория: Теория сложности]] | [[Категория: Теория сложности]] | ||
== Детерминированные и недетерминированные вычисления, сложность по времени и по памяти == | == Детерминированные и недетерминированные вычисления, сложность по времени и по памяти == | ||
| − | *[[Сложностные классы | + | === Базовые определения === |
| + | *[[Сложностные классы]] | ||
| + | *[[Вычисления с оракулом]] | ||
=== Классы P и NP, NP-полнота === | === Классы P и NP, NP-полнота === | ||
*[[Класс P]] | *[[Класс P]] | ||
*[[Недетерминированные вычисления]] | *[[Недетерминированные вычисления]] | ||
| − | *[[Классы NP | + | *[[Классы NP, coNP, Σ₁, Π₁]] |
*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]] | *[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]] | ||
| − | *[[ | + | *[[Сведение по Куку задачи факторизации к языку из 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)]] | ||
| − | *[[Классы L, NL, coNL. NL-полнота | + | *[[PS-полнота задачи Generalized geography]] |
| + | *[[Классы L, NL, coNL]] | ||
| + | *[[Полнота относительно L-сведения. NL-полнота. P-полнота]] | ||
| + | *[[Теорема Иммермана]] | ||
| + | *[[Классы EXP и NEXP]] | ||
=== Полиномиальная иерархия === | === Полиномиальная иерархия === | ||
*[[Классы PH, Σ и Π]] | *[[Классы PH, Σ и Π]] | ||
*[[Теоремы о коллапсе полиномиальной иерархии]] | *[[Теоремы о коллапсе полиномиальной иерархии]] | ||
| + | |||
| + | === Классы задач подсчета === | ||
| + | *[[Классы Sharp P, Sharp P-Complete|Классы #P, #P-Complete]] | ||
== Схемная сложность == | == Схемная сложность == | ||
| Строка 36: | Строка 57: | ||
== Вероятностные сложностные классы == | == Вероятностные сложностные классы == | ||
| + | === Основные классы === | ||
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]] | *[[Вероятностные вычисления. Вероятностная машина Тьюринга]] | ||
| − | *[[Классы | + | *[[Классы RP и coRP]] |
| − | *[[ | + | *[[Класс ZPP]] |
| + | *[[Классы BPP и PP]] | ||
| + | *[[Соотношение вероятностных классов]] | ||
| + | *[[Лемма Шварца-Зиппеля]] | ||
*[[Теорема Лаутемана]] | *[[Теорема Лаутемана]] | ||
| + | *[[Теорема Валианта-Вазирани]] | ||
=== Интерактивные протоколы === | === Интерактивные протоколы === | ||
*[[Интерактивные протоколы. Класс IP. Класс AM]] | *[[Интерактивные протоколы. Класс IP. Класс AM]] | ||
| − | |||
*[[Арифметизация булевых формул с кванторами]] | *[[Арифметизация булевых формул с кванторами]] | ||
| − | *[[ | + | *[[Теорема о соотношении coNP и IP]] |
*[[Теорема Шамира]] | *[[Теорема Шамира]] | ||
*[[Семейство универсальных попарно независимых хеш-функций]] | *[[Семейство универсальных попарно независимых хеш-функций]] | ||
| − | *[[Протокол | + | *[[Протокол Голдвассер-Сипсера для оценки размера множества]] |
=== Probabilistically checkable proofs === | === Probabilistically checkable proofs === | ||
*[[PCP-система]] | *[[PCP-система]] | ||
| + | *[[Эквивалентность PCP-теоремы и теоремы о трудности аппроксимации]] | ||
*[[PCP-теорема]] | *[[PCP-теорема]] | ||
| − | |||
---- | ---- | ||
[[Теория сложности (старая трешовая версия)|Вот сюда]] можно подсматривать, но злоупотреблять не рекомендуется. | [[Теория сложности (старая трешовая версия)|Вот сюда]] можно подсматривать, но злоупотреблять не рекомендуется. | ||
Текущая версия на 19:42, 4 сентября 2022
Содержание
Детерминированные и недетерминированные вычисления, сложность по времени и по памяти
Базовые определения
Классы 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
Полиномиальная иерархия
Классы задач подсчета
Схемная сложность
- Схемная сложность и класс P/poly
- Теорема Карпа — Липтона
- Классы NC и AC
- Теорема о непринадлежности XOR классу AC⁰
Вероятностные сложностные классы
Основные классы
- Вероятностные вычисления. Вероятностная машина Тьюринга
- Классы RP и coRP
- Класс ZPP
- Классы BPP и PP
- Соотношение вероятностных классов
- Лемма Шварца-Зиппеля
- Теорема Лаутемана
- Теорема Валианта-Вазирани
Интерактивные протоколы
- Интерактивные протоколы. Класс IP. Класс AM
- Арифметизация булевых формул с кванторами
- Теорема о соотношении coNP и IP
- Теорема Шамира
- Семейство универсальных попарно независимых хеш-функций
- Протокол Голдвассер-Сипсера для оценки размера множества
Probabilistically checkable proofs
Вот сюда можно подсматривать, но злоупотреблять не рекомендуется.
