Теория сложности — различия между версиями
Kirillova (обсуждение | вклад) (→Сложность по памяти, классы PS, L, NL, coNL) |
(→Сложность по памяти, классы PS, L, NL, coNL) |
||
| Строка 23: | Строка 23: | ||
*[[Теорема Сэвича. Совпадение классов NPS и PS]] | *[[Теорема Сэвича. Совпадение классов NPS и PS]] | ||
*[[PS-полнота языка верных булевых формул с кванторами (TQBF)]] | *[[PS-полнота языка верных булевых формул с кванторами (TQBF)]] | ||
| − | *[[Классы L, NL, coNL | + | *[[Классы L, NL, coNL]] |
| + | *[[NL-полнота задачи о достижимости]] | ||
| + | *[[Теорема Иммермана]] | ||
=== Полиномиальная иерархия === | === Полиномиальная иерархия === | ||
Версия 20:41, 4 июня 2012
Эта статья находится в разработке!
Содержание
Детерминированные и недетерминированные вычисления, сложность по времени и по памяти
Классы P и NP, NP-полнота
- Класс P
- Недетерминированные вычисления
- Классы NP и Σ₁
- Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
- Примеры NP-полных языков. Теорема Кука
- Теоремы о временной и емкостной иерархиях
- Теорема Бейкера — Гилла — Соловэя
- Теорема Ладнера
- Теорема Левина
- Теорема Бермана — Форчуна
- Теорема Махэни
Сложность по памяти, классы PS, L, NL, coNL
- Класс PS. Связь класса PS с другими классами теории сложности
- Теорема Сэвича. Совпадение классов NPS и PS
- PS-полнота языка верных булевых формул с кванторами (TQBF)
- Классы L, NL, coNL
- NL-полнота задачи о достижимости
- Теорема Иммермана
Полиномиальная иерархия
Схемная сложность
- Схемная сложность и класс P/poly
- Теорема Карпа — Липтона
- Классы NC и AC
- Теорема о непринадлежности XOR классу AC⁰
Вероятностные сложностные классы
- Вероятностные вычисления. Вероятностная машина Тьюринга
- Классы BPPweak и BPPstrong
- Уменьшение ошибки в классе RP
- Теорема Лаутемана
Интерактивные протоколы
- Интерактивные протоколы. Класс IP. Класс AM
- Связь классов IP и AM друг с другом и с другими классами языков
- Арифметизация булевых формул с кванторами
- Лемма о соотношении coNP и IP
- Теорема Шамира
- Семейство универсальных попарно независимых хеш-функций
- Протокол Голдвассера-Сипсера для оценки размера множества
Probabilistically checkable proofs
Вот сюда можно подсматривать, но злоупотреблять не рекомендуется.
