Co-NP-полная задача — в теории алгоритмов задача с ответом «да» или «нет», принадлежащая классу co-NP, такая, что любая задача из этого класса может быть сведена к ней за полиномиальное время.

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

Любая co-NP-полная задача является дополнением некоторой NP-полной задачи. Существуют задачи, которые принадлежат как классу NP, так и классу co-NP, например, любая задача из класса P и задача факторизации. При этом неизвестно, совпадают ли классы NP и co-NP или, что эквивалентно, существует ли задача, одновременно являющаяся NP- и co-NP-полной.

Задача разрешимости ${\displaystyle C}$ является co-NP-полной, если она сама лежит в классе co-NP и любая другая задача из co-NP полиномиально сводится к ней. Другими словами, для любой задачи ${\displaystyle L}$ из класса co-NP существует алгоритм, который за полиномиальное время преобразует входные данные задачи ${\displaystyle L}$ во входные данные задачи ${\displaystyle C}$ таким образом, чтобы ответ к новой задаче совпадал с ответом исходной. Следовательно, если для задачи ${\displaystyle C}$ существует полиномиальный алгоритм, то любая задача из класса co-NP может быть решена за полиномиальное время.

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

• Кормен Т. Лейзерсон Ч. Ривест Р. Алгоритмы : Построение и анализ: Учебник: пер. с англ.. — Москва МЦНМО. Архивная копия от 21 августа 2019 на Wayback Machine

Классы сложности алгоритмов
Считаются лёгкими	DLOGTIME[англ.] AC0[англ.] ACC0[англ.] TC0[англ.] L SL[англ.] RL[англ.] NL NC SC[англ.] CC[англ.] P P-complete[англ.] ZPP RP BPP BQP EQP APX
Предполагаются сложными	UP[англ.] NP NP-complete co-NP co-NP-complete AM[англ.] MA[англ.] QMA PH ⊕P[англ.] PP #P #P-complete[англ.] IP[англ.] PSPACE PSPACE-complete[англ.]
Считаются сложными	EXPTIME NEXPTIME[англ.] EXPSPACE[англ.] 2-EXPTIME[англ.] ELEMENTARY[англ.] R PR[англ.] RE[англ.] RE-complete[англ.] Co-RE[англ.] Co-RE-complete[англ.] ALL[англ.]