со-НП

Нерешенная проблема в информатике :

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

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

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

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

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

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

Задача L является co-NP-полной тогда и только тогда, когда L принадлежит co-NP и для любой задачи из co-NP существует полиномиальное по времени сведение этой задачи к задаче L.

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

P , класс задач, разрешимых за полиномиальное время, является подмножеством как NP, так и co-NP. P считается строгим подмножеством в обоих случаях. Поскольку P замкнуто относительно дополнения, а NP и co-NP являются дополнительными, оно не может быть строгим в одном случае и не строгим в другом: если P равно NP, оно также должно быть равно co-NP, и наоборот. ^[2]

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

co-NP является подмножеством PH , которое, в свою очередь, является подмножеством PSPACE .

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

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