со-НП

Нерешенная задача в информатике :

${\textsf {NP}}\ {\overset {?}{=}}\ {\textsf {co-NP}}$

(еще нерешенные проблемы по информатике)

В сложности вычислений теории co-NP — это класс сложности . Проблема решения X является членом co-NP тогда и только тогда, когда ее дополнение X находится в классе сложности NP . Класс можно определить следующим образом: проблема принятия решения находится в co-NP тогда и только тогда, когда для каждого no » полиномиальной длины -экземпляра у нас есть « сертификат и существует алгоритм с полиномиальным временем, который можно использовать для проверки любого предполагаемого сертификат.

То есть co-NP — это набор задач решения, где существует полином $p(n)$ ограниченная полиномиальным временем, и машина Тьюринга M, , что для каждого экземпляра x x такая является не -экземпляром тогда и только тогда, когда: для некоторого возможного сертификата c длины, ограниченной $p(n)$машина Тьюринга M принимает пару ( x , c ) .

проблемы

Основная статья: Дополнение (сложность)

В то время как задача NP спрашивает, является ли данный экземпляр да -экземпляром, ее дополнение спрашивает, является ли экземпляр не -экземпляром, что означает, что дополнение находится в со-NP. Любой да -экземпляр исходной задачи NP становится не -экземпляром для ее дополнения, и наоборот.

Неудовлетворенность

Дополнительная информация: Неудовлетворительное ядро.

Примером NP-полной проблемы является проблема булевой выполнимости ли данная булева формула : выполнима (существует ли возможный входной сигнал, для которого формула выдает истинное значение)? Дополнительная проблема спрашивает: «Для данной логической формулы является ли она невыполнимой (все возможные входные данные формулы выводят ложь)?». Поскольку это дополнение к проблеме выполнимости, сертификат для экземпляра no такой же, как и для экземпляра yes из исходной задачи NP: набор логических присвоений переменных, которые делают формулу истинной. С другой стороны, сертификат « да » для дополнительной задачи будет столь же сложным, как и «нет » для исходной проблемы выполнимости NP.

Двойные задачи

Основная статья: Двойственность (оптимизация)

ко-NP-полнота

Основная статья: совместное NP-полное

Проблема L является ко-NP-полной тогда и только тогда, когда L находится в ко-NP и для любой проблемы в ко-NP существует полиномиальное сведение этой проблемы к L .

Редукция тавтологии

ли формула в логике высказываний Определение того, является тавтологией, является ко-NP-полной: то есть, если формула дает истинное значение при каждом возможном присвоении ее переменным.

Отношения с другими классами

Дополнительная информация: Класс сложности.

Включения классов сложности, включая P , NP , co-NP, BPP , P/poly , PH и PSPACE.

P , класс задач, решаемых за полиномиальное время, является подмножеством как NP, так и co-NP. В обоих случаях P считается строгим подмножеством (и, очевидно, не может быть строгим в одном случае и нестрогим в другом).

Также считается, что NP и co-NP неравны. Если это так, то никакая NP-полная задача не может находиться в ко-NP, и никакая ко-NP-полная задача не может быть в NP. Это можно показать следующим образом. Предположим, от противного, что существует NP-полная задача X , находящаяся в ко-NP. Поскольку все проблемы в NP можно свести к X , отсюда следует, что для каждой проблемы в NP мы можем построить недетерминированную машину Тьюринга , которая решает ее дополнение за полиномиальное время; то есть, ${\textsf {NP}}\subseteq {\textsf {co-NP}}$. Отсюда следует, что множество дополнений задач в NP является подмножеством множества дополнений задач в ко-NP; то есть, ${\textsf {co-NP}}\subseteq {\textsf {NP}}$. Таким образом ${\textsf {co-NP}}={\textsf {NP}}$. Доказательство того, что ни одна ко-NP-полная задача не может находиться в NP, если ${\textsf {NP}}\neq {\textsf {co-NP}}$ является симметричным.

co-NP — это подмножество PH , которое само по себе является подмножеством PSPACE .

Целочисленная факторизация

Основная статья: Целочисленная факторизация

Примером задачи, которая, как известно, принадлежит как NP, так и co-NP (но не известно, что она находится в P), является факторизация целых чисел . : по данным целым положительным числам m и n определить, имеет ли m коэффициент меньше n и больше единицы. Членство в НП очевидно; если у m есть такой фактор, то этот фактор сам по себе является сертификатом. Принадлежность к co-NP также проста: можно просто перечислить простые множители числа m , все они больше или равны n , достоверность которых проверяющий может подтвердить путем умножения и теста на простоту AKS . В настоящее время неизвестно, существует ли алгоритм факторизации с полиномиальным временем, что эквивалентно тому, что факторизация целых чисел осуществляется в P, и, следовательно, этот пример интересен как одна из наиболее естественных задач, которые, как известно, существуют в NP и co-NP, но не известны для быть в П.

Внешние ссылки

• Зоопарк сложности : coNP