#дневниклекций
Сегодня была вторая лекция про NP-полноту. Обсуждали несколько конкретных задач, а также задачи поиска. Изучили вот что:
- Задачи, связанные с гамильтоновыми путями: HAMPATH (существует ли гамильтонов путь в орграфе из s в t), HAMCYCLE (существует ли гамильтонов цикл в орграфе), аналоги для неориентированных графов, задача коммивояжёра.
- Сведение HAMPATH к HAMCYCLE: неправильность очевидной конструкции и её исправление.
- Сведение 3SAT к HAMCYCLE: гаджеты-ромбы, гирлянда и вершины для скобок, обоснование корректности сведения
- Сведение HAMPATH к UHAMPATH: недостаточность снятие ориентации, конструкция с утроением вершин
- Сведение UHAMCYCLE к TSP
- Задача NAE-SAT о существовании набора, при котором в каждой скобке есть истинные и ложные литералы. Сведение 3SAT к NAE-SAT
- Сведение NAE-SAT к 3COL
- Задачи поиска: определение, сводимость по Левину
- Сводимость задач поиска к задачам распознавания на примере задачи о клике. Рекурсивная конструкция через самосводимость
- Кратко о задачах подсчёта и аппроксимации (подробнее в следующий раз)