复杂度类 coNP

前缀 co 表示对语言取补。NP 的存在证书站在是实例一侧；coNP 把同一套存在证书放到否实例一侧。若直接交换一台非确定机器的接受和拒绝状态，得到的是“所有分支原先都拒绝”一类全称语义，并不会自动变成标准的存在接受分支机器。

一个语言同时属于 NP 与 coNP，说明正反答案都各有短且可核验的证据。验证容易仍不等于寻找容易，因此这个交集并不自动等于 P；目前既不知道 NP 是否等于 coNP，也没有证明它们不同。

TAUT 的反例证书 ​

TAUT 收集对每个赋值都为真的布尔公式。公式不是重言式时，一份使它为假的赋值就是多项式长度证书。例如 $p\vee q$ 在 $(p,q)=(0,0)$ 时为假，验证器代入两位即可确认它不属于 TAUT；而

对四种赋值都为真，没有反例证书。于是 $\overline{\mathrm{TAUT}}\in \mathrm{NP}$，从而 $\mathrm{TAUT}\in \mathrm{coNP}$。同理，UNSAT 的补语言是 SAT，所以 UNSAT 属于 coNP；这并不声称不可满足公式本身已有已知的一般多项式短证明。

已知包含与开放分离 ​

P 对补封闭，故

从 $L\in \mathrm{NP}$ 不能推出 $L\in \mathrm{coNP}$。素数判定曾因正反两侧都有精巧证书而成为交集中的典型例子，后来才由 AKS 算法证明属于 P；这个历史不能反向证明整个交集等于 P。

coNP 对多项式时间 many-one 归约公理库多项式时间归约Polynomial-time reduction · Karp reduction用一个多项式时间可计算的变换把问题 A 的实例转换为问题 B 的实例。的逆像封闭。若 $A{\le }_m^{p}B$ 且 $B\in \mathrm{coNP}$，同一个映射还满足

由于 $\bar{B}\in \mathrm{NP}$，计算 $f(x)$ 后验证其证书便知 $\bar{A}\in \mathrm{NP}$，所以 $A\in \mathrm{coNP}$。

这一步解释了重要的坍缩结论：若某个 NP-complete 语言 $C$ 也属于 coNP，则每个 $A\in \mathrm{NP}$ 都归约到 $C$，从而都属于 coNP，即 $\mathrm{NP}\subseteq \mathrm{coNP}$；再对所有语言取补得到反向包含，于是 $\mathrm{NP}=\mathrm{coNP}$。多项式层级公理库多项式层级Polynomial hierarchy · PH由交替存在和全称多项式证书或逐层 NP 预言机构成的复杂性层级。会把这一等式的影响继续传播到更高量词层。