常见的复杂性类定义形式为：可以被某一种计算模型 M 使用 O(f(n)) 的某种资源（如时间、空间）所解决的问题的集合。（其中 n 为输入编码的长度）。经典的复杂性类例如 P：可以被确定性图灵机在多项式时间内解决的决定性问题的集合、NP：可以被非确定性图灵机在多项式时间内解决的决定性问题的集合、PSPACE（确定性多项式空间类）、Logspace（确定性对数空间类）等。