Теория сложности (старая трешовая версия) — различия между версиями
(→Практика 2) |
(→Практика 2) |
||
| Строка 14: | Строка 14: | ||
== Практика 2 == | == Практика 2 == | ||
| − | *[[Понятие NP-трудной и NP-полной задачи]] | + | *[[Понятие <tex>NP</tex>-трудной и <tex>NP</tex>-полной задачи]] |
| − | *[[NP-полнота задачи BH_{1N}]] | + | *[[NP-полнота задачи <tex>BH_{1N}</tex>]] |
*[[NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ]] | *[[NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ]] | ||
Версия 00:55, 16 марта 2010
Содержание
Лекция 1
- Класс DSPACE
- Класс DTIME
- Теорема о емкостной иерархии
- Теорема о временной иерархии
- Сведение по Карпу
- Сведение по Куку
Практика 1
Лекция 2
Практика 2
- [[Понятие -трудной и -полной задачи]]
- [[NP-полнота задачи ]]
- NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ
Лекция 3
Практика 3
- NP-полнота задач о гамильтоновом цикле и пути в графах
- NP-полнота задачи о сумме подмножества
- NP-полнота задачи о рюкзаке
