形式陈述

对语言 $L\subseteq\Sigma^*$$L\subseteq {\mathrm{\Sigma }}^{\ast }$，记补语言 $\overline L=\Sigma^*\setminus L$$\bar{L}={\mathrm{\Sigma }}^{\ast }\setminus L$。定义

$$ \mathrm{coNP}=\{L:\overline L\in\mathrm{NP}\}. $$$$\mathrm{coNP}=\{L:\bar{L}\in \mathrm{NP}\}.$$

等价地，$L\in\mathrm{coNP}$$L\in \mathrm{coNP}$ 表示“不属于 $L$$L$”的实例具有可在多项式时间验证的短证书。

直觉

NP 强调“是”实例有短证明；coNP 强调“否”实例有短证明。前缀 co 表示对语言取补，而不是把 NP 中的算法或机器简单倒转输出。

例子与边界

命题公式不可满足性 UNSAT 属于 coNP，因为其补问题 SAT 属于 NP。$\mathrm P$$\mathrm{P}$ 对补封闭，所以 $\mathrm P\subseteq\mathrm{NP}\cap\mathrm{coNP}$$\mathrm{P}\subseteq \mathrm{NP}\cap \mathrm{coNP}$。目前不知道 $\mathrm{NP}=\mathrm{coNP}$$\mathrm{NP}=\mathrm{coNP}$，也不知道二者不同。

推论与应用

coNP 用于表达等价性、恒真性和最优性证明等“排除反例”的问题。若某个 NP-complete 问题也属于 coNP，则会推出 $\mathrm{NP}=\mathrm{coNP}$$\mathrm{NP}=\mathrm{coNP}$。

参考资料

• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009，§2.1。
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，§7.3。