Алгоритмы для задачи выполнимости: локальный поиск

Локальный поиск: поиск выполняющего набора в шаре радиуса r за O∗(3^r); оценки O∗(3^n/2) и O∗(1.5^n) с помощью покрытия шарами радиуса n/2 и n/4. Лекция №9 в курсе “Алгоритмы для NP трудных задач“ (осень 2013). Преподаватель курса: Александр Куликов. Страница лекции на сайте CS центра: