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

Лекция 1

• Класс DSPACE
• Теорема о емкостной иерархии

Лекция 2

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

Лекция 3

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

Практика 3

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

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

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

Лекция 4

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