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