Теория сложности — различия между версиями
Leugenea (обсуждение | вклад) (Убран редирект) |
Leugenea (обсуждение | вклад) (Добавлены темы первой волны) |
||
| Строка 1: | Строка 1: | ||
| + | {{В разработке}} | ||
| + | [[Категория: Теория сложности]] | ||
| + | |||
| + | *[[Сложностные классы. Вычисления с оракулом]] | ||
| + | *[[Класс P]] | ||
| + | *[[Недетерминированные вычисления. Классы NP и Σ₁]] | ||
| + | *[[Сведение по Карпу. Трудные и полные задачи]] | ||
| + | *[[Примеры NP-полных языков. Теорема Кука]] | ||
| + | *[[Теоремы о временной и емкостной иерархиях]] | ||
| + | *[[Теорема Бейкера — Гилла — Соловэя]] | ||
| + | *[[Теорема Ладнера]] | ||
| + | *[[Теорема Левина]] | ||
| + | *[[Теорема Махэни (лайт)]] | ||
| + | *[[Теорема Махэни]] | ||
| + | *[[Класс PS. Теорема Сэвича. Совпадение классов NPS и PS]] | ||
| + | *[[PS-полнота языка верных булевых формул с кванторами (TQBF)]] | ||
| + | *[[Классы L, NL, coNL. NL-полнота задачи о достижимости]] | ||
| + | *[[Классы PH, Σ и Π]] | ||
| + | *[[Теоремы о коллапсе полиномиальной иерархии]] | ||
| + | *[[Схемная сложность и класс P/poly]] | ||
| + | *[[Теорема Карпа — Липтона]] | ||
| + | *[[Классы NC и AC]] | ||
| + | *[[Теорема о не принадлежности XOR классу AC⁰]] | ||
Версия 20:03, 4 апреля 2012
Эта статья находится в разработке!
- Сложностные классы. Вычисления с оракулом
- Класс P
- Недетерминированные вычисления. Классы NP и Σ₁
- Сведение по Карпу. Трудные и полные задачи
- Примеры NP-полных языков. Теорема Кука
- Теоремы о временной и емкостной иерархиях
- Теорема Бейкера — Гилла — Соловэя
- Теорема Ладнера
- Теорема Левина
- Теорема Махэни (лайт)
- Теорема Махэни
- Класс PS. Теорема Сэвича. Совпадение классов NPS и PS
- PS-полнота языка верных булевых формул с кванторами (TQBF)
- Классы L, NL, coNL. NL-полнота задачи о достижимости
- Классы PH, Σ и Π
- Теоремы о коллапсе полиномиальной иерархии
- Схемная сложность и класс P/poly
- Теорема Карпа — Липтона
- Классы NC и AC
- Теорема о не принадлежности XOR классу AC⁰
