Co-NP и асимметрия NP
Чтобы расширить свое представление об этом общем классе задач, вернемся к тем определениям, на которых базировался класс NP.
Мы уже видели, что понятие эффективного сертифицирующего алгоритма не предполагает конкретного алгоритма для фактического решения задачи, который бы превосходил метод «грубой силы».
А теперь еще одно наблюдение: определение эффективного сертифицирования (а следовательно, и NP) по своей сути асимметрично.
Из отрицания этого утверждения мы видим, что входная строка представляет экземпляр с отрицательной сертификацией в том, и только в том случае, если для всех коротких t выполняется B(s, t) = нет.
Все это близко к нашим интуитивным представлениям о NP: если экземпляр сертифицируется положительно, мы можем привести короткое доказательство этого факта.
Но для экземпляров с отрицательной сертификацией определение не гарантирует соответствующего короткого доказательства; ответ отрицателен просто потому, что не удается найти строку, которая бы служила доказательством. Вспомните вопрос из раздела 8.3: если набор условий невыполним, какие «доказательства» могли бы быстро убедить вас в невыполнимости задачи?
Для каждой задачи X существует естественная дополняющая задача : для всех входных строк s мы говорим, что в том, и только в том случае, если . Следует заметить, что если, то, так как из алгоритма A, решающего X, мы можем просто построить алгоритм , который выполняет A, а затем «инвертирует» его ответ.
Но при этом совершенно не очевидно, что из должно следовать, что. Вместо этого задача обладает другим свойством: для всех s выполняется в том, и только в том случае, если для всех t длины не более, B(s, t) = нет. Это принципиально иное определение, которое невозможно обойти
простым «инвертированием» вывода эффективного сертифицирующего алгоритма B для получения. Проблема в том, что «существует t» в определении NP превращается в «для всех t», и это серьезное изменение.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу