Теория сложности — различия между версиями
Kirelagin (обсуждение | вклад) |
AndrewD (обсуждение | вклад) |
||
| Строка 12: | Строка 12: | ||
*[[Теорема Ладнера]] | *[[Теорема Ладнера]] | ||
*[[Теорема Левина]] | *[[Теорема Левина]] | ||
| − | *[[Теорема | + | *[[Теорема Бермана — Форчуна]] |
*[[Теорема Махэни]] | *[[Теорема Махэни]] | ||
*[[Класс PS. Теорема Сэвича. Совпадение классов NPS и PS]] | *[[Класс PS. Теорема Сэвича. Совпадение классов NPS и PS]] | ||
Версия 23:51, 27 апреля 2012
Эта статья находится в разработке!
- Сложностные классы. Вычисления с оракулом
- Класс P
- Недетерминированные вычисления. Классы NP и Σ₁
- Сведение по Карпу. Трудные и полные задачи
- Примеры NP-полных языков. Теорема Кука
- Теоремы о временной и емкостной иерархиях
- Теорема Бейкера — Гилла — Соловэя
- Теорема Ладнера
- Теорема Левина
- Теорема Бермана — Форчуна
- Теорема Махэни
- Класс PS. Теорема Сэвича. Совпадение классов NPS и PS
- PS-полнота языка верных булевых формул с кванторами (TQBF)
- Классы L, NL, coNL. NL-полнота задачи о достижимости
- Классы PH, Σ и Π
- Теоремы о коллапсе полиномиальной иерархии
- Схемная сложность и класс P/poly
- Теорема Карпа — Липтона
- Классы NC и AC
- Теорема о не принадлежности XOR классу AC⁰
Вот сюда можно подсматривать, но злоупотреблять не рекомендуется.
