Введение

В теории сложности вычислительные задачи, являющиеся 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, что является критическим основанием для теоремы Маэни.

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

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

Пример

Одним из примеров co-NP-полной задачи является тавтология – проблема определения, является ли данная булева формула тавтологией; то есть, приводит ли любое возможное присваивание значений «истина» или «ложь» переменным к истинному высказыванию. Эта задача тесно связана с задачей выполнимости булевых формул (SAT), которая спрашивает, существует ли хотя бы одно такое присваивание, и является NP-полной.