#дневниклекций
Сегодня были 3 слабо связанные между собой темы: задачи подсчёта, задачи аппроксимации и пэддинг. Изучили следующее:
- Постановка задачи подсчёта: по входу x нужно найти число таких y, что V(x,y)=1. Класс #P для полиномиальных V. Понятие NP-трудности для задач подсчёта. Сводимость по Куку.
- (Очевидная) NP-трудность задачи подсчёта, соответствующей NP-полной задаче распознавания. Пример, когда задача распознавания полиномиальна, а задача подсчёта NP-трудна: число простых циклов в ориентированном графе. Построение сводимости: гаджет-"конфета", замена рёбер на него, подсчёт числа циклов в двух случаях, итоговая конструкция сводимости.
- Пара слов про задачу о перманенте.
- Постановка задач оптимизации и аппроксимации. Два варианта в каждом случае: поиск оптимума и точки оптимума. Пример, когда задача точной оптимизации NP-трудна, а аппроксимации - полиномиальна (Задача о вершинном покрытии). Вариации задачи коммивояжёра: общая (NP-трудная для любой точности), метрическая (полиномиально разрешимая с множителем 3/2, алгоритм Кристофидеса-Сердюкова), евклидова (полиномиально разрешимая с любой точностью, алгоритм Ароры).
- Классы задач оптимизации и аппроксимации: NPO, APX, PTAS, FPTAS.
- Понятие об NP-трудности задач аппроксимации. Формулировка теоремы для задачи MAX3SAT: существование приближённого алгоритма с множителем 7/8 и NP-трудность аппроксимации с множителем 7/8+ε (PCP-теорема).
- Метод пэддинга (изменения масштаба задачи). Общая идея и два приложения: если P=NP, то EXP=NEXP, а также NP≠E (вывод из E≠EXP).