反NP

在计算复杂度理论上，反NP类是复杂度类的其中一类。

定义

一个问题${\displaystyle {\mathcal {X}}}$是反NP的成员，若且唯若，它的补全${\displaystyle {\mathcal {X}}^{\rm {C}}}$必定是在复杂度NP；用数学符号来写，${\displaystyle \mathbf {CoNP} :=\{L|L^{\rm {C}}\in \mathbf {NP} \}}$。

简单来说，反NP复杂度，是高效率而又可核实地证明命题为错的组群，当中的佼佼者是立即找到反例存在。

其中一个NP完全问题的例子是子集合加总问题：给一个整数集合，问是否存在某个非空子集中的数字和为0？ 例：给定集合{−7, −3, −2, 5, 8}，答案是是，因为子集合{−3, −2, 5}的数字和是0。

补全问题在反NP中就会要求：给有限的整数集，是否每个非空子集之总和皆不为0？你的证明只要必须给出事例，叙述"没有"指定求和到零的一个非空子集，而这证明必须可以在合理时间内验证。

与其他复杂度的关系

复杂度P，是多项式时间可解的问题集合，是一个NP和反NP的子集。P通常认定是一个在此两类别下的严格子集（但无法验证是落在两个集合的哪一边）。NP和反NP通常认为是不相等的。如果那样，NP完全问题将不会落在反NP问题中，且反NP完全问题将不会落在NP中。

本问题可由下述步骤粗略证明：假设有个NP完全问题${\displaystyle {\mathcal {X}}}$处于反NP问题的集合中，由于所有NP问题可被变换成${\displaystyle {\mathcal {X}}}$问题，因此我们可以为所有NP问题建造一个可在多项式时间判定其补性质的非确定型图灵机，意即NP是反NP的子集。因此NP问题的补集合是一个反NP问题的补集合的子集，意即反NP是NP的子集。由于我们已知NP是反NP的子集，因此表示这两个集合是一样的，这证明了没有反NP完全问题可在NP类之中的性质是对称的（Symmetrical）。

用数学符号严格证明：假设一个问题${\displaystyle {\mathcal {X}}}$是NP完全，${\displaystyle \mathbf {NP} =\mathbf {CoNP} }$，若且唯若${\displaystyle {\mathcal {X}}\in \mathbf {CoNP} }$。以下的证明是不能从以上文字直接看得出：

${\displaystyle \Rightarrow }$

若${\displaystyle \mathbf {NP} =\mathbf {CoNP} }$，${\displaystyle {\mathcal {X}}\in \mathbf {NP} \Rightarrow {\mathcal {X}}\in \mathbf {CoNP} }$

${\displaystyle \Leftarrow }$

${\displaystyle \mathbf {NP} \subseteq \mathbf {CoNP} }$：如果${\displaystyle {\mathcal {L}}\in \mathbf {NP} }$。很明显地，若${\displaystyle {\mathcal {X}}}$是NP完全，自然${\displaystyle {\mathcal {X}}}$ 是NP难，${\displaystyle {\mathcal {L}}\leq _{p}{\mathcal {X}}}$，所以${\displaystyle {\mathcal {L}}^{\mathrm {C} }\leq _{p}{\mathcal {X}}^{\mathrm {C} }}$。但${\displaystyle {\mathcal {X}}\in \mathbf {CoNP} }$亦即代表${\displaystyle {\mathcal {X}}^{\mathrm {C} }\in \mathbf {NP} }$，所以${\displaystyle {\mathcal {L}}^{\mathrm {C} }\in \mathbf {NP} }$，最终 ${\displaystyle {\mathcal {L}}\in \mathbf {CoNP} }$。

${\displaystyle \mathbf {NP} \supseteq \mathbf {CoNP} }$：${\displaystyle {\mathcal {X}}\in \mathbf {CoNP} \Rightarrow {\mathcal {X}}^{\mathrm {C} }\in \mathbf {NP} \Rightarrow {\mathcal {X}}^{\mathrm {C} }\in \mathbf {CoNP} \Rightarrow ({\mathcal {X}}^{\mathrm {C} })^{\mathrm {C} }={\mathcal {X}}\in \mathbf {NP} }$

如果一个问题可被证同时为NP与反NP，则通常我们将会视作本问题不是NP完全命题的强力假设（若非如此，则NP相等于反NP）。

应用

一个同时在NP与反NP集合的有名问题是整数分解：给两个正整数m与n，决定m是否有小于n且大于1的因数。

第一个问题的方法很清晰：如果m的确存在一个满足条件的因子，则长除法即可验证；另一个问题的方法就困难且精妙多了：你必须将m的所有质数因子列出，并为每个因子提供质数性质的证明。

整数因子分解常与质数性质问题混淆在一起，整数因子化据信是NP或反NP，而质数问题落在类别P^[1]。

文内注释

1. 参考: http://www.math.princeton.edu/~annals/issues/2004/Sept2004/Agrawal.pdf （页面存档备份，存于互联网档案馆）

参考资料

• （英文） 复杂度类动物园：反NP

外部链接

• Complexity Zoo: coNP