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