NP-полные задачи

Задачи поиска, сведения, доказательство NP-полноты задач выполнимости, 3-выполнимости, задачи о независимом множестве, задачи о вершинном покрытии. Лекция №2 в курсе “Алгоритмы для NP-трудных задач“ (осень 2013). Преподаватель: Александр Куликов. Страница лекции на сайте CS центра (с презентацией):