Общая стратегия доказательства NP-полноты новых задач
В оставшейся части этой главы мы в основном будем заниматься изучением других NP-полных задач. В частности, мы обсудим другие разновидности сложных вычислительных задач и докажем, что некоторые представители этих категорий являются NP-полными.
Основная стратегия доказательства NP-полноты новой задачи X выглядит примерно так:
- Доказать, что X Ѯ NP.
- Выбрать задачу Y, которая заведомо является NP-полной.
- Доказать, что Y ≤P X.
Ранее было замечено, что многие сведения Y ≤P X состоят из преобразования заданного экземпляра Y в экземпляр X с тем же ответом. Для решения X используется одно обращение к «черному ящику». При использовании подобных сведений приведенная выше стратегия превращается в следующий план доказательства NP-полноты.
- Доказать, что X Ѯ NP.
- Выбрать задачу Y, которая заведомо является NP-полной.
- Рассмотреть произвольный экземпляр sY задачи Y и показать, как построить за полиномиальное время экземпляр sX задачи X, обладающий следующими свойствами.
- Если sY является экземпляром Y, на который дается ответ «да», то и sX является экземпляром X, на который дается ответ «да».
- Если sX является экземпляром X, на который дается ответ «да», то и sУ является экземпляром Y, на который дается ответ «да».
Другими словами, тем самым устанавливается, что sY и sX имеют одинаковый ответ.
Проводились исследования, направленные на изучение различий между сведениями с полиномиальным временем для специальной структуры (обращение к «черному ящику» с одним вопросом и буквальное использование полученного ответа) и более общей концепцией сведения с полиномиальным временем, при которых обращения к «черному ящику» могут производиться многократно.
(Более ограниченный вариант сведения называется сведением по Карпу, тогда как более общий вариант называется сведением по Куку или сведением по Тьюрингу с полиномиальным временем.) Здесь эти различия рассматриваться не будут.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу