В теории сложности вычислений , совместно NP является классом сложности . Проблема решения X является членом сотрудничества НП тогда и только тогда , когда его дополнение X находится в сложности класса NP . Класс может быть определена следующим образом : проблема решение в сотрудничестве НП точно , если для любого нет -instance х есть « сертификат » , который полиномиальный алгоритм время можно использовать для проверки того, что х не является не -instance.
Эквивалентно, co-NP - это набор задач принятия решений, где существует многочлен p (n) и машина Тьюринга с ограниченным полиномиальным временем, такая, что для каждого экземпляра x , x является экземпляром `` да '' тогда и только тогда, когда: для каждого возможного сертификата c длины, ограниченной p (n) , машина Тьюринга принимает пару ( x , c ). [1]
Проблемы [ править ]
Дополнение любой проблемы в NP - это проблема в co-NP. Примером NP-полной проблемы является проблема выполнимости схемы : существует ли для булевой схемы возможный вход, для которого схема выдает истинное значение? В дополнительной задаче задается вопрос: «Все ли возможные входы на выходе схемы являются ложными для данной логической схемы?». Это в co-NP, потому что сертификат отсутствия экземпляра с полиномиальным временем представляет собой набор входных данных, которые делают выход истинным.
Примером проблемы, которая, как известно, принадлежит как NP, так и co-NP (но не известно, что она находится в P), является целочисленная факторизация : заданные положительные целые числа m и n , определить, имеет ли m множитель меньше n и больше единицы . Членство в НП ясно; если у m есть такой коэффициент, то он сам по себе является сертификатом. Членство в co-NP также простое: можно просто перечислить простые множители m , все больше или равные n, которые проверяющий может подтвердить как действительные с помощью умножения и теста простоты AKS. В настоящее время неизвестно, существует ли алгоритм факторизации с полиномиальным временем, что эквивалентно целочисленной факторизации в P, и, следовательно, этот пример интересен как одна из наиболее естественных проблем, известных как NP и co-NP, но не известная для быть в П. [ ссылка ]
Проблема L является со-NP-полным , если и только если L в сотрудничестве НП и для любой проблемы в сотрудничестве НП существует сокращение полиномиального времени от этой проблемы до L . Пример такой задачи состоит в определении того, если формула в логике высказываний является тавтология : то есть, если формула принимает значение истинно под каждое возможным присвоением переменных. [1]
Отношение к другим классам [ править ]
P , класс задач, решаемых за полиномиальное время, является подмножеством как NP, так и co-NP. P считается строгим подмножеством в обоих случаях (и, очевидно, не может быть строгим в одном случае и не строгим в другом).
NP и co-NP также считаются неравными. [2] Если это так, то никакая NP-полная проблема не может быть в co-NP, и никакая co-NP-полная проблема не может быть в NP. [3] Это можно показать следующим образом. Предположим, что существует NP-полная проблема X , лежащая в co-NP. Поскольку все проблемы из NP сводятся к X , отсюда следует, что для каждой проблемы из NP мы можем построить недетерминированную машину Тьюрингакоторый определяет его дополнение за полиномиальное время; т.е. NP ⊆ co-NP. Из этого следует, что множество дополнений проблем в NP является подмножеством множества дополнений проблем в co-NP; т.е. co-NP ⊆ NP. Таким образом, co-NP = NP. Доказательство того, что никакая ко-NP-полная проблема не может быть в NP, если NP ≠ co-NP симметрична.
Ссылки [ править ]
- ^ а б Арора, Санджив; Варак, Вооз (2009). Теория сложности: современный подход . Издательство Кембриджского университета. п. 56. ISBN 978-0-521-42426-4.
- ^ Хопкрофт, Джон Э. (2000). Введение в теорию автоматов, языки и вычисления (2-е издание) . Бостон: Эддисон-Уэсли. ISBN 0-201-44124-1.Глава. 11.
- ^ Голдрайх, Одед (2010). P, NP и NP-полнота: основы вычислительной сложности . Издательство Кембриджского университета . п. 155. ISBN 9781139490092.
Внешние ссылки [ править ]
- Зоопарк сложности : coNP
