反NP 编辑
在计算复杂度理论上，反NP类是复杂度类的其中一类。
1
相关
交替式图灵机是计算复杂度理论中定义的一种非确定型图灵机。与一般非确定型图灵机不同，交替式图灵机将接受语言的规则一般化到NP和反NP。交替式图灵机的概念由Chandra和Stockmeyer于1976年提出。
计算复杂度理论中，多项式谱系是一个复杂度系列。它从P、NP和反NP复杂度类逐级产生至预言机。它类似于数理逻辑中算数阶层和分析阶层，只不过是由逐级放宽资源限制而产生的。
交替式图灵机是计算复杂度理论中定义的一种非确定型图灵机。与一般非确定型图灵机不同，交替式图灵机将接受语言的规则一般化到NP和反NP。交替式图灵机的概念由Chandra和Stockmeyer于1976年提出。