Теория сложности (старая трешовая версия) — различия между версиями
(→Лекция 1) |
|||
| Строка 12: | Строка 12: | ||
== Лекция 2 == | == Лекция 2 == | ||
*[[Теорема Кука]] | *[[Теорема Кука]] | ||
| + | |||
| + | == Практика 2 == | ||
| + | *[[NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ]] | ||
== Лекция 3 == | == Лекция 3 == | ||
Версия 11:13, 15 марта 2010
Содержание
Лекция 1
- Класс DSPACE
- Класс DTIME
- Теорема о емкостной иерархии
- Теорема о временной иерархии
- Сведение по Карпу
- Сведение по Куку
Практика 1
Лекция 2
Практика 2
Лекция 3
Практика 3
- NP-полнота задач о гамильтоновом цикле и пути в графах
- NP-полнота задачи о сумме подмножества
- NP-полнота задачи о рюкзаке
