Теория сложности (старая трешовая версия)

Лекция 1

• Класс DSPACE
• Класс DTIME
• Теорема о емкостной иерархии
• Теорема о временной иерархии
• Сведение по Карпу
• Сведение по Куку

Практика 1

• Сведение по Куку задачи факторизации к языку из NP

Лекция 2

• Теорема Кука

Практика 2

• [[Понятие [math]NP[/math]-трудной и [math]NP[/math]-полной задачи]]
• [[NP-полнота задачи [math]BH_{1N}[/math]]]
• NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ

Лекция 3

• Теорема Ладнера
• Теорема Левина
• Теорема Бейкера-Гилла-Соловэя

Практика 3

• NP-полнота задач о гамильтоновом цикле и пути в графах
• NP-полнота задачи о сумме подмножества
• NP-полнота задачи о рюкзаке

Практика, которой на самом деле не было

• NP-полнота задачи о раскраске графа

Лекция 4

• PS-полнота задачи Generalized geography