В теории сложности вычислений co-NP — это класс сложности . Проблема решения X является членом co-NP тогда и только тогда, когда ее дополнение X находится в классе сложности NP . Класс можно определить следующим образом: проблема принятия решения находится в co-NP тогда и только тогда, когда для каждого no -экземпляра у нас есть « сертификат » полиномиальной длины и существует алгоритм с полиномиальным временем, который можно использовать для проверки любого предполагаемого сертификат.
То есть co-NP — это набор задач решения, где существуют полиномиальная и полиномиальная машина Тьюринга M , ограниченная по полиномиальному времени , такая, что для каждого экземпляра x x является не -экземпляром тогда и только тогда, когда: для некоторого возможного сертификата c длина ограничена , машина Тьюринга M принимает пару ( x , c ) . [1]
В то время как задача NP спрашивает, является ли данный экземпляр да -экземпляром, ее дополнение спрашивает, является ли данный экземпляр не -экземпляром, что означает, что дополнение находится в со-NP. Любой да -экземпляр исходной задачи NP становится не -экземпляром для ее дополнения, и наоборот.
Примером NP-полной проблемы является проблема булевой выполнимости : выполнима ли данная булева формула (существует ли возможный входной параметр, для которого формула выдает true)? Дополнительная проблема спрашивает: «Для данной логической формулы является ли она невыполнимой (все возможные входные данные формулы выводят ложь)?». Поскольку это дополнение к проблеме выполнимости, сертификат для экземпляра no такой же, как и для экземпляра yes из исходной задачи NP: набор логических присвоений переменных, которые делают формулу истинной. С другой стороны, сертификат «да » для дополнительной задачи будет столь же сложным, как и « нет » для исходной проблемы выполнимости NP. [ нужны разъяснения ]
Проблема L является ко-NP-полной тогда и только тогда, когда L находится в ко-NP и для любой проблемы в ко-NP существует полиномиальное сведение этой проблемы к L .
Определение того, является ли формула в логике высказываний тавтологией, является ко-NP-полной: то есть, если формула дает истинное значение при каждом возможном присвоении ее переменным. [1]
P , класс задач, решаемых за полиномиальное время, является подмножеством как NP, так и co-NP. В обоих случаях P считается строгим подмножеством (и, очевидно, не может быть строгим в одном случае и нестрогим в другом). [ нужна цитата ]
Также считается, что NP и co-NP неравны. [2] Если это так, то никакая NP-полная задача не может находиться в ко-NP, и никакая ко-NP-полная задача не может находиться в NP. [3] Это можно показать следующим образом. Предположим, от противного, что существует NP-полная задача X , находящаяся в ко-NP. Поскольку все проблемы в NP можно свести к X , отсюда следует, что для каждой проблемы в NP мы можем построить недетерминированную машину Тьюринга , которая решает ее дополнение за полиномиальное время; то есть, . Отсюда следует, что множество дополнений задач в NP является подмножеством множества дополнений задач в ко-NP; то есть, . Таким образом . Доказательство того, что ни одна ко-NP-полная задача не может находиться в NP, если она симметрична.
co-NP — это подмножество PH , которое само по себе является подмножеством PSPACE .
Примером проблемы, которая, как известно, принадлежит как NP, так и co-NP (но не известно, что она находится в P), является факторизация целых чисел : по заданным положительным целым числам m и n определить, имеет ли m коэффициент меньше n и больше единицы. . Членство в НП очевидно; если у m есть такой фактор, то этот фактор сам по себе является сертификатом. Членство в co-NP также простое: можно просто перечислить простые множители m , все они больше или равны n , достоверность которых проверяющий может подтвердить путем умножения и теста на простоту AKS . В настоящее время неизвестно, существует ли алгоритм факторизации с полиномиальным временем, что эквивалентно факторизации целых чисел в P, и, следовательно, этот пример интересен как одна из наиболее естественных задач, которые, как известно, существуют в NP и co-NP, но не известны для быть в П. [ нужна ссылка ]
