В теории сложности вычислительные проблемы, которые являются co-NP-полными, являются теми, которые являются самыми сложными проблемами в co-NP , в том смысле, что любая проблема в co-NP может быть переформулирована как частный случай любой co-NP-полной проблемы с только полиномиальными накладными расходами. Если P отличается от co-NP, то все co-NP-полные проблемы неразрешимы за полиномиальное время. Если существует способ быстро решить co-NP-полную проблему, то этот алгоритм может быть использован для быстрого решения всех co-NP проблем.
Каждая co-NP-полная задача является дополнением NP -полной задачи. Некоторые задачи есть как в NP , так и в co-NP , например, все задачи в P или целочисленной факторизации . Однако неизвестно, равны ли множества, хотя неравенство считается более вероятным. Подробнее см. co-NP и NP-полная .
В 1979 году Форчун показал, что если какой-либо разреженный язык является co-NP-полным (или даже просто co-NP-трудным), то P = NP [1] , что является критическим основанием для теоремы Махани .
Задача принятия решений C является co-NP-полной, если она принадлежит co-NP и если каждая задача из co-NP является полиномиально-однозначной, сводимой к ней. [2] Это означает, что для каждой co-NP задачи L существует полиномиальный по времени алгоритм, который может преобразовать любой экземпляр L в экземпляр C с тем же значением истинности . Как следствие, если бы у нас был полиномиальный по времени алгоритм для C , мы могли бы решить все co-NP задачи за полиномиальное время.
Одним из примеров co-NP-полной проблемы является тавтология , проблема определения, является ли данная булева формула тавтологией; то есть, дает ли каждое возможное присвоение истинных/ложных значений переменным истинное утверждение. Это тесно связано с проблемой выполнимости булевой формулы , которая спрашивает, существует ли хотя бы одно такое присвоение, и является NP-полной. [2]