反NP

在计算复杂度理论上，反NP类是复杂度类的其中一类。反NP复杂度，是高效率而又可核实地证明命题为错的组群，当中的佼佼者是立即找到反例存在。一个问题是反NP的成员，当且仅当，它的补全必定是在复杂度NP；用数学符号来写，。