Теория сложности (старая трешовая версия) — различия между версиями
Vadim (обсуждение | вклад) (→Лекция 6) |
|||
| Строка 45: | Строка 45: | ||
== Лекция 6 == | == Лекция 6 == | ||
*[[NL-полнота задачи о достижимости в графе]] | *[[NL-полнота задачи о достижимости в графе]] | ||
| + | *[[Классы EXP, NEXP. Полнота языков EXP и NEXP]] | ||
*[[Теорема о связи вопросов EXP=NEXP и P=NP]] | *[[Теорема о связи вопросов EXP=NEXP и P=NP]] | ||
*[[Теорема Иммермана]] | *[[Теорема Иммермана]] | ||
Версия 22:34, 7 апреля 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
- NL-полнота задачи о достижимости в графе
- Классы EXP, NEXP. Полнота языков EXP и NEXP
- Теорема о связи вопросов EXP=NEXP и P=NP
- Теорема Иммермана
