复杂度类 coNP

前缀 co 表示对语言取补。NP 的存在证书站在是实例一侧；coNP 把同一套存在证书放到否实例一侧。直接交换一台非确定机器的接受和拒绝状态后，新机器仍按存在接受分支判定，所以它接受的条件是“至少一个分支原先拒绝”。补语言要求的却是“所有分支原先都拒绝”。例如原计算树同时有一条接受分支和一条拒绝分支，交换前后机器都会接受，因此这种交换不能直接判定补语言。

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

TAUT 的反例证书 ​

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

对四种赋值都为真，没有反例证书。这里让 TAUT、SAT 与 UNSAT 都只包含合法布尔公式编码，并使用多项式时间的语法检查。在全集 ${\mathrm{\Sigma }}^{\ast }$ 中，非法编码也属于 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 预言机构成的复杂性层级。会把这一等式的影响继续传播到更高量词层。