在计算复杂度理论中，一个复杂度类指的是一群复杂度类似的问题的集合。一个典型的复杂度类的定义有以下：
1
多项式时间在计算复杂度理论中，指的是一个问题的计算时间
m
{\displaystyle m}
不大于问题大小
n
{\displaystyle n}
的多项式倍数。任何抽象机器都拥有一复杂度类，此类包括可于此机器以多项式时间求解的问题。
在计算复杂度理论与递归论中，预言机，又称谕示机，是一种抽象电脑，用来研究决定型问题。可以被视为一个或多个黑盒子的图灵机，这个黑盒子的功能是可以在单一运算之内解答特定问题。预言者可以解答的问题，根据给定可以是任何复杂度类之内的问题。甚至可以使用不可判定问题，像是停机问题。
在计算复杂度理论内，若有A与B两个复杂度类，且AB = A；或者说, A 在B成为他的神谕机器之后的复杂度等同于A，则我们说复杂度类别B比A要来的"低"。这陈述代表着一个可以解决问题类别A的机器，在获得了在单位时间内解决问题类别B的能力之后，并没有增加多余的计算能力。特别是，这代表着如果B类别低于A类别，则B必然包含在A里面。
在可计算性理论与计算复杂性理论中，所谓的归约是将某个计算问题转换为另一个问题的过程。可用归约法定义某些问题的复杂度类。
在计算复杂度理论上，反NP类是复杂度类的其中一类。
在计算复杂度理论上，反NP类是复杂度类的其中一类。
在可计算性理论与计算复杂性理论中，所谓的归约是将某个计算问题转换为另一个问题的过程。可用归约法定义某些问题的复杂度类。
在复杂度类里面, 一个建议字串是一种以原本输入的长度n来对图灵机新增加的输入，并且不是输入的资料本身。如果存在一个多项式时间图灵机具有特性如下：对任何自然数n，存在一个建议字串A，长度是f，并且对任何长度是n的输入x，机器M在给予x和A为输入的状态下可以正确判断x是否在这个问题上正确，我们说这个决定型问题在复杂度类 P/f里面。
在可计算性理论与计算复杂性理论中，所谓的归约是将某个计算问题转换为另一个问题的过程。可用归约法定义某些问题的复杂度类。
Mini wiki
