Co-NP и асимметрия NP - NP-полнота и вычислительная неразрешимость

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

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

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

Для каждой задачи Л'существует естественная дополняющая задача для всех входных строк s мы говорим, что в том, и только в том случае, если . Следует заметить, что если X ∈ Р, то так как из алгоритма A, решающего X, мы можем просто построить алгоритм который выполняет А, а затем “инвертирует” его ответ.

Но при этом совершенно не очевидно, что из X ∈ NР должно следовать, что Вместо этого задача обладает другим свойством: для всех s выполняется в том, и только в том случае, если для всех t длины не более p(|s|), B(s, t) = нет. Это принципиально иное определение, которое невозможно обойти простым “инвертированием” вывода эффективного сертифицирующего алгоритма В для получения Проблема в том, что “существует t” в определении NP превращается в “для всех t”, и это серьезное изменение.

Существует класс задач, параллельных NP, спроектированных для моделирования этой проблемы; ему присвоено достаточно естественное название co-NP. Задачах принадлежит co-NP в том, и только в том случае, если дополняющая задача принадлежит NP. Но мы не знаем наверняка, что NP и co-NP различны; можем только спросить:

(8.25) Выполняется ли NP = co-NP?

И снова принято считать, что NP ≠ co-NP: из того, что экземпляры задач с положительной сертификацией имеют короткие доказательства, совершенно не следует, что экземпляры с отрицательной сертификацией также должны иметь короткие доказательства.

Доказательство NP Ф co-NP стало бы еще более важным шагом, чем доказательство P Ф NP, по следующей причине:

(8.26) Если NP ≠ co-NP, то P ≠ NP.

Доказательство. На самом деле мы докажем обратное утверждение: из P = NP следует NP = co-NP. Здесь важно то, что множество P замкнуто относительно дополнения; следовательно, если P = NP, то множество NP также будет замкнуто относительно дополнения. Или в более формальном изложении, начиная с предположения P = NP, имеем

и

Из этого следует, что NP ⊆ co-NP и co-NP ⊆ NР, а значит, NP = co-NP. ■

Хорошая характеризация: класс NP ∩ co-NP

Если задача X принадлежит как NP, так и co-NP, то она обладает следующим полезным свойством: для ответа “да” существует короткое доказательство; для ответа “нет” также существует короткое доказательство. Задачи, принадлежащие этому пересечению NP ∩ co-NP, называются имеющими хорошую характеризацию, так как для решения всегда существует хороший сертификат.

Это понятие напрямую соответствует некоторым результатам, которые мы видели ранее. Например, возьмем задачу определения того, содержит ли потоковая сеть поток с величиной как минимум v, для некоторого значения v. Чтобы доказать, что ответ на этот вопрос положительный, достаточно продемонстрировать поток, достигающий этой величины; это свойство согласуется с принадлежностью задачи NP. Но также можно доказать и отрицательный ответ: можно продемонстрировать разрез, пропускная способность которого строго меньше v. Этот дуализм между экземплярами с положительной и отрицательной сертификацией является сутью теоремы о максимальном потоке и минимальном разрезе.

Аналогичным образом теорема Холла для сочетаний из раздела 7.5 доказывала, что задача о двудольном идеальном паросочетании принадлежит NP ∩ co-NP: мы могли предъявить либо идеальное паросочетание, либо множество вершин A ⊆ X, для которого общее количество соседей A строго меньше |A|.

Если задача X находится в P, то она принадлежит как NP, так и co-NP; следовательно, P ⊆ NP ∩ co-NP. Интересно, что как наше доказательство теоремы о максимальном потоке и минимальном разрезе, так и наше доказательство теоремы Холла идут рука об руку с доказательствами более сильных результатов о том, что задачи о максимальном потоке и двудольном паросочетании являются задачами из P. Тем не менее хорошие характеризации сами по себе настолько элегантны, что их отдельная формулировка дает значительную концептуальную основу для рассуждения об этих задачах.

Естественно, нам хотелось бы знать, существует ли задача с хорошей характеризацией, например без алгоритма с полиномиальным временем. Однако этот вопрос также остается открытым:

(8.27) Выполняется ли P = NP ∩ co-NP?

В отличие от вопросов (8.11) и (8.25), общественное мнение по этому поводу неоднородно. Отчасти это объясняется существованием многих случаев, в которых у задач отыскивались нетривиальные хорошие характеризации; а затем (порой через много лет) выяснялось, что задача имеет алгоритм с полиномиальным временем.