со-NP-полный
В теории сложности вычислительные задачи, которые являются ко-NP-полными, — это те, которые являются самыми сложными проблемами в ко-NP , в том смысле, что любая проблема в ко-NP может быть переформулирована как частный случай любой ко-NP-полной задачи. только с полиномиальными накладными расходами. Если P отличается от co-NP, то все ко-NP-полные задачи не разрешимы за полиномиальное время. Если существует способ быстрого решения ко-NP-полной задачи, то этот алгоритм можно использовать для быстрого решения всех ко-NP-полных задач.
Каждая ко-NP-полная задача является дополнением NP -полной задачи. Есть некоторые проблемы как в NP , так и в co-NP , например, все проблемы в P или целочисленной факторизации . Однако неизвестно, равны ли множества, хотя неравенство считается более вероятным. Более подробную информацию см . в разделах co-NP и NP-complete .
В 1979 году компания Fortune показала, что если какой-либо разреженный язык является ко-NP-полным (или даже просто ко-NP-сложным), то P = NP , [1] критическое обоснование теоремы Махани .
Формальное определение
[ редактировать ]Проблема решения C является ко-NP-полной, если она находится в ко-NP и если каждая проблема в ко-NP сводится к ней за полиномиальное время «многие-один» . [2] Это означает, что для каждой проблемы со-NP L существует алгоритм с полиномиальным временем, который может преобразовать любой экземпляр L в экземпляр C с тем же значением истинности . Как следствие, если бы у нас был алгоритм для C с полиномиальным временем , мы могли бы решить все проблемы co-NP за полиномиальное время.
Пример
[ редактировать ]Одним из примеров ко-NP-полной проблемы является тавтология , проблема определения того, является ли данная булева формула тавтологией; то есть, дает ли каждое возможное присвоение переменных значений true/false истинное утверждение. Это тесно связано с проблемой булевой выполнимости , которая спрашивает, существует ли хотя бы одно такое присваивание, и является NP-полной. [2]
Ссылки
[ редактировать ]- ^ Форчун, С. (1979). «Заметка о редких комплектах» (PDF) . SIAM Journal по вычислительной технике . 8 (3): 431–433. дои : 10.1137/0208034 . hdl : 1813/7473 .
- ^ Перейти обратно: а б Арора, Санджив; Барак, Боаз (2009). Теория сложности: современный подход . Издательство Кембриджского университета. ISBN 978-0-521-42426-4 .