反NP

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

定义

一个问题是反NP的成员，当且仅当，它的补全必定是在复杂度NP；用数学符号来写，。
简单来说，反NP复杂度，是高效率而又可核实地证明命题为错的组群，当中的佼佼者是立即找到反例存在。
其中一个NP完全问题的例子是子集合加总问题：给一个整数集合，问是否存在某个非空子集中的数字和为0？ 例：给定集合{−7, −3, −2, 5, 8}，答案是是，因为子集合{−3, −2, 5}的数字和是0。
补全问题在反NP中就会要求：给有限的整数集，是否每个非空子集有一个非零总和？你的证明只要必须给出事例，叙述"没有"指定求和到零的一个非空子集，而这证明必须可以在合理时间内验证。

应用

一个同时在NP与反NP集合的有名问题是整数分解：给两个正整数m与n，决定m是否有小于n且大于1的因数。
第一个问题的方法很清晰：如果m的确存在一个满足条件的因子，则长除法即可验证；另一个问题的方法就困难且精妙多了：你必须将m的所有质数因子列出，并为每个因子提供质数性质的证明。
整数因子分解常与质数性质问题混淆在一起，整数因子化据信是NP或反NP，而质数问题落在类别P。