Участник:Shersh/Тикеты к 6ому терму — различия между версиями
Shersh (обсуждение | вклад) м (→Детерминированные и недетерминированные вычисления, сложность по времени и по памяти) |
Shersh (обсуждение | вклад) (проставлены номера разделов) |
||
| Строка 1: | Строка 1: | ||
| − | == Детерминированные и недетерминированные вычисления, сложность по времени и по памяти == | + | == 1. Детерминированные и недетерминированные вычисления, сложность по времени и по памяти == |
| − | === Базовые определения === | + | === 1. Базовые определения === |
*[[Сложностные классы]] | *[[Сложностные классы]] | ||
*[[Вычисления с оракулом]] | *[[Вычисления с оракулом]] | ||
| − | === Классы P и NP, NP-полнота === | + | === 2. Классы P и NP, NP-полнота === |
*[[Класс P]] | *[[Класс P]] | ||
*[[Недетерминированные вычисления]] | *[[Недетерминированные вычисления]] | ||
| Строка 19: | Строка 19: | ||
*[[Теорема Махэни]] | *[[Теорема Махэни]] | ||
| − | === Сложность по памяти, классы PS, L, NL, coNL === | + | === 3. Сложность по памяти, классы PS, L, NL, coNL === |
*[[Класс PS. Связь класса PS с другими классами теории сложности]] | *[[Класс PS. Связь класса PS с другими классами теории сложности]] | ||
*[[Теорема Сэвича. Совпадение классов NPS и PS]] | *[[Теорема Сэвича. Совпадение классов NPS и PS]] | ||
| Строка 27: | Строка 27: | ||
*[[Теорема Иммермана]] | *[[Теорема Иммермана]] | ||
| − | === Полиномиальная иерархия === | + | === 4. Полиномиальная иерархия === |
*[[Классы PH, Σ и Π]] | *[[Классы PH, Σ и Π]] | ||
*[[Теоремы о коллапсе полиномиальной иерархии]] | *[[Теоремы о коллапсе полиномиальной иерархии]] | ||
| − | == Схемная сложность == | + | == 2. Схемная сложность == |
*[[Схемная сложность и класс P/poly]] | *[[Схемная сложность и класс P/poly]] | ||
*[[Теорема Карпа — Липтона]] | *[[Теорема Карпа — Липтона]] | ||
| Строка 37: | Строка 37: | ||
*[[Теорема о непринадлежности XOR классу AC⁰]] | *[[Теорема о непринадлежности XOR классу AC⁰]] | ||
| − | == Вероятностные сложностные классы == | + | == 3. Вероятностные сложностные классы == |
| − | === Основные классы === | + | === 1. Основные классы === |
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]] | *[[Вероятностные вычисления. Вероятностная машина Тьюринга]] | ||
*[[Классы RP и coRP]] | *[[Классы RP и coRP]] | ||
| Строка 46: | Строка 46: | ||
*[[Теорема Лаутемана]] | *[[Теорема Лаутемана]] | ||
| − | === Интерактивные протоколы === | + | === 2. Интерактивные протоколы === |
*[[Интерактивные протоколы. Класс IP. Класс AM]] | *[[Интерактивные протоколы. Класс IP. Класс AM]] | ||
*[[Арифметизация булевых формул с кванторами]] | *[[Арифметизация булевых формул с кванторами]] | ||
| Строка 54: | Строка 54: | ||
*[[Протокол Голдвассер-Сипсера для оценки размера множества]] | *[[Протокол Голдвассер-Сипсера для оценки размера множества]] | ||
| − | === Probabilistically checkable proofs === | + | === 3. Probabilistically checkable proofs === |
*[[PCP-система]] | *[[PCP-система]] | ||
*[[Эквивалентность PCP-теоремы и теоремы о трудности аппроксимации]] | *[[Эквивалентность PCP-теоремы и теоремы о трудности аппроксимации]] | ||
*[[PCP-теорема]] | *[[PCP-теорема]] | ||
Версия 22:37, 24 февраля 2016
Содержание
1. Детерминированные и недетерминированные вычисления, сложность по времени и по памяти
1. Базовые определения
2. Классы P и NP, NP-полнота
- Класс P
- Недетерминированные вычисления
- Классы NP и Σ₁
- Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
- NP-полнота BH1N
- Теорема Кука
- Примеры NP-полных языков
- Теоремы о временной и емкостной иерархиях
- Теорема Бейкера — Гилла — Соловэя
- Теорема Ладнера
- Теорема Левина
- Теорема Бермана — Форчуна
- Теорема Махэни
3. Сложность по памяти, классы PS, L, NL, coNL
- Класс PS. Связь класса PS с другими классами теории сложности
- Теорема Сэвича. Совпадение классов NPS и PS
- PS-полнота языка верных булевых формул с кванторами (TQBF)
- Классы L, NL, coNL
- Полнота относительно L-сведения. NL-полнота. P-полнота
- Теорема Иммермана
4. Полиномиальная иерархия
2. Схемная сложность
- Схемная сложность и класс P/poly
- Теорема Карпа — Липтона
- Классы NC и AC
- Теорема о непринадлежности XOR классу AC⁰
3. Вероятностные сложностные классы
1. Основные классы
- Вероятностные вычисления. Вероятностная машина Тьюринга
- Классы RP и coRP
- Класс ZPP
- Классы BPP и PP
- Соотношение вероятностных классов
- Теорема Лаутемана
2. Интерактивные протоколы
- Интерактивные протоколы. Класс IP. Класс AM
- Арифметизация булевых формул с кванторами
- Теорема о соотношении coNP и IP
- Теорема Шамира
- Семейство универсальных попарно независимых хеш-функций
- Протокол Голдвассер-Сипсера для оценки размера множества
