со-НП
В сложности вычислений теории co-NP — это класс сложности . Проблема решения X является членом co-NP тогда и только тогда, когда ее дополнение X находится в классе сложности NP . Класс можно определить следующим образом: проблема принятия решения находится в co-NP тогда и только тогда, когда для каждого no » полиномиальной длины -экземпляра у нас есть « сертификат и существует алгоритм с полиномиальным временем, который можно использовать для проверки любого предполагаемого сертификат.
То есть co-NP — это набор задач решения, в которых существует полином ограниченная полиномиальным временем, и машина Тьюринга M, , что для каждого экземпляра x x такая является не -экземпляром тогда и только тогда, когда: для некоторого возможного сертификата c длины, ограниченной , машина Тьюринга M принимает пару ( x , c ) . [1]
Дополнительные проблемы
[ редактировать ]В то время как задача NP спрашивает, является ли данный экземпляр да -экземпляром, ее дополнение спрашивает, является ли экземпляр не -экземпляром, что означает, что дополнение находится в со-NP. Любой да -экземпляр исходной задачи NP становится не -экземпляром для ее дополнения, и наоборот.
неудовлетворённость
[ редактировать ]Примером NP-полной проблемы является проблема булевой выполнимости ли данная булева формула : выполнима (существует ли возможный входной сигнал, для которого формула выдает истинное значение)? Дополнительная проблема спрашивает: «Для данной логической формулы является ли она невыполнимой (все возможные входные данные формулы выводят ложь)?». Поскольку это дополнение к проблеме выполнимости, сертификат для экземпляра no такой же, как и для экземпляра yes из исходной задачи NP: набор логических присвоений переменных, которые делают формулу истинной. С другой стороны, сертификат « да » для дополнительной задачи (какую бы форму он ни принимал) будет столь же сложным, как и для «нет » исходной проблемы выполнимости NP.
ко-NP-полнота
[ редактировать ]Проблема L является ко-NP-полной тогда и только тогда, когда L находится в ко-NP и для любой проблемы в ко-NP существует полиномиальное сведение этой проблемы к L .
Сокращение тавтологии
[ редактировать ]ли формула в логике высказываний Определение того, является тавтологией, является ко-NP-полной: то есть, если формула дает истинное значение при каждом возможном присвоении ее переменным. [1]
Отношения с другими классами
[ редактировать ]
P , класс задач, решаемых за полиномиальное время, является подмножеством как NP, так и co-NP. В обоих случаях P считается строгим подмножеством. Поскольку P замкнуто относительно дополнения, а NP и со-NP дополняют друг друга, оно не может быть строгим в одном случае и нестрогим в другом: если P равно NP, оно также должно быть равно со-NP, и наоборот. [2]
Также считается, что NP и co-NP неравны. [3] Если это так, то никакая NP-полная задача не может находиться в ко-NP, и никакая ко-NP-полная задача не может быть в NP. [4] Это можно показать следующим образом. Предположим, от противного, что существует 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, но не известны для быть в П. [5]
Ссылки
[ редактировать ]- ^ Jump up to: Перейти обратно: а б Арора, Санджив; Барак, Вооз (2009). Теория сложности: современный подход . Издательство Кембриджского университета. п. 56. ИСБН 978-0-521-42426-4 .
- ^ Батлер, Эльвира (2004). «П против НП» . Монографии Королевской академии наук Сарагосы . 26 :57–68.
- ^ Хопкрофт, Джон Э. (2000). Введение в теорию автоматов, языки и вычисления (2-е изд.). Бостон: Аддисон-Уэсли. ISBN 0-201-44124-1 . Глава. 11.
- ^ Гольдрейх, Одед (2010). P, NP и NP-полнота: основы сложности вычислений . Издательство Кембриджского университета . п. 155. ИСБН 9781139490092 .
- ^ Ааронсон, Скотт (2016). « П ≟ NP » (PDF) . В Нэше Джон Форбс-младший ; Рассиас, Майкл Т. (ред.). Открытые задачи по математике . Международное издательство Спрингер. стр. 1–122. дои : 10.1007/978-3-319-32162-2_1 . ISBN 9783319321622 . См. раздел 2.2.4 Факторизация и изоморфизм графов, стр. 19–20 книги (стр. 17–18 связанной версии).