反NP

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

一个问题${\displaystyle \mathcal{X}}$是反NP的成员，当且仅当，它的补全${\displaystyle {\mathcal{X}}^{\mathrm{C}}}$必定是在复杂度NP；用数学符号来写，${\displaystyle \mathbf{C}\mathbf{o}\mathbf{N}\mathbf{P}:=\{L|L^{\mathrm{C}}\in <!--\; \in \; -->\mathbf{N}\mathbf{P}\}}$。

简单来说，反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{N}\mathbf{P}=\mathbf{C}\mathbf{o}\mathbf{N}\mathbf{P}}$，当且仅当${\displaystyle \mathcal{X}\in <!--\; \in \; -->\mathbf{C}\mathbf{o}\mathbf{N}\mathbf{P}}$。以下的证明是不能从以上文字直接看得出：

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

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

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

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