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