Теория сложности (старая трешовая версия) — различия между версиями
Miron (обсуждение | вклад) м (добавлена практика 7) |
(→Практика 6) |
||
| Строка 46: | Строка 46: | ||
*[[Классы Sigma_i]] | *[[Классы Sigma_i]] | ||
*[[Классы Pi_i]] | *[[Классы Pi_i]] | ||
| + | *[[Класс PH]] | ||
*[[Полиномиальная иерархия]] | *[[Полиномиальная иерархия]] | ||
*[[Теорема о коллапсе полиномиальной иерархии]] | *[[Теорема о коллапсе полиномиальной иерархии]] | ||
| + | |||
== Практика 7 == | == Практика 7 == | ||
*[[Класс BPP]] | *[[Класс BPP]] | ||
Версия 10:55, 4 апреля 2010
Содержание
Лекция 1
- Класс DSPACE
- Класс DTIME
- Теорема о емкостной иерархии
- Теорема о временной иерархии
- Сведение по Карпу
- Сведение по Куку
- Класс P
- Класс NP
- Класс coNP
Практика 1
Лекция 2
Практика 2
- Понятие NP-трудной и NP-полной задачи
- NP-полнота задачи BH1N
- NP-полнота задачи о выполнимости булевой формулы в форме КНФ
- NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ
- NP-полнота задачи о клике
- NP-полнота задачи о независимом множестве
- NP-полнота задачи о вершинном покрытии
Лекция 3
Практика 3
- NP-полнота задач о гамильтоновом цикле и пути в графах
- NP-полнота задачи о сумме подмножества
- NP-полнота задачи о рюкзаке
Практика, которой на самом деле не было
Лекция 4
Практика 6
- Классы Sigma_i
- Классы Pi_i
- Класс PH
- Полиномиальная иерархия
- Теорема о коллапсе полиномиальной иерархии
