Co-NP и асимметрия NP

Чтобы расширить свое представление об этом общем классе задач, вернемся к тем определениям, на которых базировался класс NP.

Мы уже видели, что понятие эффективного сертифицирующего алгоритма не предполагает конкретного алгоритма для фактического решения задачи, который бы превосходил метод «грубой силы».

А теперь еще одно наблюдение: определение эффективного сертифицирования (а следовательно, и NP) по своей сути асимметрично.

Входная строка s представляет экземпляр с положительной сертификацией в том, и только в том случае, если существует короткое значение t, для которого B(s, t) = да.

Из отрицания этого утверждения мы видим, что входная строка представляет экземпляр с отрицательной сертификацией в том, и только в том случае, если для всех коротких t выполняется B(s, t) = нет.

Все это близко к нашим интуитивным представлениям о NP: если экземпляр сертифицируется положительно, мы можем привести короткое доказательство этого факта.

Но для экземпляров с отрицательной сертификацией определение не гарантирует соответствующего короткого доказательства; ответ отрицателен просто потому, что не удается найти строку, которая бы служила доказательством. Вспомните вопрос из раздела 8.3: если набор условий невыполним, какие «доказательства» могли бы быстро убедить вас в невыполнимости задачи?

Для каждой задачи X существует естественная дополняющая задача : для всех входных строк s мы говорим, что в том, и только в том случае, если . Следует заметить, что если, то, так как из алгоритма A, решающего X, мы можем просто построить алгоритм   , который выполняет A, а затем «инвертирует» его ответ.

Но при этом совершенно не очевидно, что из должно следовать, что. Вместо этого задача   обладает другим свойством: для всех s выполняется в том, и только в том случае, если для всех t  длины не более, B(s, t) = нет. Это принципиально иное определение, которое невозможно обойти

простым «инвертированием» вывода эффективного сертифицирующего алгоритма B для получения. Проблема в том, что «существует t» в определении NP превращается в «для всех t», и это серьезное изменение.