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