В теории сложности вычислительные задачи, которые являются ко-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] Это означает, что для каждой проблемы co-NP L существует алгоритм с полиномиальным временем, который может преобразовать любой экземпляр L в экземпляр C с тем же значением истинности . Как следствие, если бы у нас был алгоритм для C с полиномиальным временем , мы могли бы решить все проблемы co-NP за полиномиальное время.
Одним из примеров ко-NP-полной проблемы является тавтология , проблема определения того, является ли данная булева формула тавтологией; то есть, дает ли каждое возможное присвоение значений true/false переменным истинное утверждение. Это тесно связано с проблемой булевой выполнимости , которая спрашивает, существует ли хотя бы одно такое присваивание, и является NP-полной. [2]