со-НП-полный - co-NP-complete

В теории сложности вычислительные задачи, которые являются ко-NP-полными, - это те, которые являются наиболее сложными проблемами в co-NP , в том смысле, что любую проблему в co-NP можно переформулировать как частный случай любой co-NP-полной задачи. только с полиномиальными накладными расходами. Если P отличается от co-NP, то все совместные NP-полные проблемы не разрешимы за полиномиальное время. Если существует способ быстро решить совместную NP-полную проблему, то этот алгоритм можно использовать для быстрого решения всех совместных NP-задач.

Каждая ко-NP-полная проблема является дополнением к NP-полной проблеме. Есть некоторые проблемы как в NP, так и в co-NP , например, все проблемы в P или целочисленной факторизации . Однако неизвестно, равны ли наборы, хотя неравенство считается более вероятным. См. Co-NP и NP-complete для более подробной информации.

В 1979 году компания Fortune показала, что если какой-либо разреженный язык является NP-полным (или даже просто NP-трудным), то P = NP , что является критическим основанием теоремы Махани .

Формальное определение

Проблема решение C совместно NP-полной , если она находится в сотрудничестве НП и если каждая проблема в сотрудничестве НП является полиномиальное время многих один приводимым к нему. Это означает, что для каждой задачи L co-NP существует алгоритм полиномиального времени, который может преобразовать любой экземпляр L в экземпляр C с тем же значением истинности . Как следствие, если бы у нас был алгоритм с полиномиальным временем для C , мы могли бы решить все задачи co-NP за полиномиальное время.

Пример

Одним из примеров ко-NP-полной проблемы является тавтология , проблема определения, является ли данная булева формула тавтологией; то есть, дает ли каждое возможное присвоение переменных истинное / ложное значение истинное утверждение. Это тесно связано с проблемой логической выполнимости , которая спрашивает, существует ли хотя бы одно такое присваивание, и является NP-полной.

Рекомендации

  1. Перейти ↑ Fortune, S. (1979). «Примечание о разреженных полных наборах» (PDF) . SIAM Journal on Computing . 8 (3): 431–433. DOI : 10.1137 / 0208034 . hdl : 1813/7473 .
  2. ^ а б Арора, Санджив; Варак, Вооз (2009). Теория сложности: современный подход . Издательство Кембриджского университета. ISBN   978-0-521-42426-4 .

Внешние ссылки