在计算复杂性理论中，通常将计算问题按照难度分成不同的类，这就是复杂性类。也就是说，复杂性类是一些具有类似复杂度的问题的集合。
常见的复杂性类定义形式为：可以被某一种计算模型 M 使用 O(f(n)) 的某种资源（如时间、空间）所解决的问题的集合。（其中 n 为输入编码的长度）。经典的复杂性类例如 P：可以被确定性图灵机在多项式时间内解决的决定性问题的集合、NP：可以被非确定性图灵机在多项式时间内解决的决定性问题的集合、PSPACE（确定性多项式空间类）、Logspace（确定性对数空间类）等。
《计算机科学技术名词 》第三版。
温馨提示：
