Теория сложности — различия между версиями
| Строка 3: | Строка 3: | ||
[[Категория: Теория сложности]] | [[Категория: Теория сложности]] | ||
| + | == Детерминированные и недетерминированные вычисления, сложность по времени и по памяти == | ||
*[[Сложностные классы. Вычисления с оракулом]] | *[[Сложностные классы. Вычисления с оракулом]] | ||
| + | |||
| + | === Классы P и NP, NP-полнота === | ||
*[[Класс P]] | *[[Класс P]] | ||
*[[Недетерминированные вычисления]] | *[[Недетерминированные вычисления]] | ||
| Строка 15: | Строка 18: | ||
*[[Теорема Бермана — Форчуна]] | *[[Теорема Бермана — Форчуна]] | ||
*[[Теорема Махэни]] | *[[Теорема Махэни]] | ||
| + | |||
| + | === Сложность по памяти, классы PS, L, NL, coNL === | ||
*[[Класс PS. Теорема Сэвича. Совпадение классов NPS и PS]] | *[[Класс PS. Теорема Сэвича. Совпадение классов NPS и PS]] | ||
*[[PS-полнота языка верных булевых формул с кванторами (TQBF)]] | *[[PS-полнота языка верных булевых формул с кванторами (TQBF)]] | ||
*[[Классы L, NL, coNL. NL-полнота задачи о достижимости]] | *[[Классы L, NL, coNL. NL-полнота задачи о достижимости]] | ||
| + | |||
| + | === Полиномиальная иерархия === | ||
*[[Классы PH, Σ и Π]] | *[[Классы PH, Σ и Π]] | ||
*[[Теоремы о коллапсе полиномиальной иерархии]] | *[[Теоремы о коллапсе полиномиальной иерархии]] | ||
| + | |||
| + | == Схемная сложность == | ||
*[[Схемная сложность и класс P/poly]] | *[[Схемная сложность и класс P/poly]] | ||
*[[Теорема Карпа — Липтона]] | *[[Теорема Карпа — Липтона]] | ||
*[[Классы NC и AC]] | *[[Классы NC и AC]] | ||
*[[Теорема о непринадлежности XOR классу AC⁰]] | *[[Теорема о непринадлежности XOR классу AC⁰]] | ||
| + | |||
| + | == Вероятностные сложностные классы == | ||
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]] | *[[Вероятностные вычисления. Вероятностная машина Тьюринга]] | ||
*[[Классы BPPweak и BPPstrong]] | *[[Классы BPPweak и BPPstrong]] | ||
*[[Уменьшение ошибки в классе RP]] | *[[Уменьшение ошибки в классе RP]] | ||
*[[Теорема Лаутемана]] | *[[Теорема Лаутемана]] | ||
| + | |||
| + | === Интерактивные протоколы === | ||
*[[Интерактивные протоколы. Класс IP. Класс AM]] | *[[Интерактивные протоколы. Класс IP. Класс AM]] | ||
*[[Связь классов IP и AM друг с другом и с другими классами языков]] | *[[Связь классов IP и AM друг с другом и с другими классами языков]] | ||
| Строка 35: | Строка 48: | ||
*[[Семейство универсальных попарно независимых хеш-функций]] | *[[Семейство универсальных попарно независимых хеш-функций]] | ||
*[[Протокол Голдвассера-Сипсера для оценки размера множества]] | *[[Протокол Голдвассера-Сипсера для оценки размера множества]] | ||
| + | |||
| + | === Probabilistically checkable proofs === | ||
*[[PCP-система]] | *[[PCP-система]] | ||
*[[PCP-теорема]] | *[[PCP-теорема]] | ||
Версия 19:14, 4 июня 2012
Эта статья находится в разработке!
Содержание
Детерминированные и недетерминированные вычисления, сложность по времени и по памяти
Классы P и NP, NP-полнота
- Класс P
- Недетерминированные вычисления
- Классы NP и Σ₁
- Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
- Примеры NP-полных языков. Теорема Кука
- Теоремы о временной и емкостной иерархиях
- Теорема Бейкера — Гилла — Соловэя
- Теорема Ладнера
- Теорема Левина
- Теорема Бермана — Форчуна
- Теорема Махэни
Сложность по памяти, классы PS, L, NL, coNL
- Класс 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
Вот сюда можно подсматривать, но злоупотреблять не рекомендуется.
