複雑性クラス（ふくざつせいクラス、英: Complexity class）は、計算複雑性理論において関連する複雑性の問題の集合を指す。典型的な複雑性クラスは以下のように定義される。抽象機械 M によりO(f(n))の計算資源 R を使って解く事が出来る問題の集合（nは入力長）
例えば、クラスNPは非決定性チューリングマシンで多項式時間で解く事が出来る決定問題の集合である。また、クラスPSPACEはチューリングマシンで多項式領域
で解く事が出来る決定問題の集合である。ここで、領域とは、実世界ではメモリ空間[1]、チューリングマシンではテープの長さと考えればよい。一部の複雑性クラスは函数問題の集合である（例えばFP）。数理論理学では表現の必要に応じて多数の複雑性クラスが定義される（記述計算量）。
ブラムの公理を使うと、完全な計算模型を参照しなくとも複雑性クラスを定義できる。 以下の表はいくつかの問題（または文法、言語）のクラスを計算複雑性理論の中で捉えて図示したものである。クラス X が Y の真部分集合である場合、X を Y の下に置き、実線でそれらを接続している。X が部分集合であっても上位と等しい可能性もある場合、破線で接続している。決定可能か決定不能かは、どちらかと言えば計算可能性理論の範疇であるが、ここでは複雑性クラスの関係を示すために入れてある。 Type 3 （正規） 以下の一覧の各複雑性クラスには補問題
複雑性クラス間の関係
複雑性クラス一覧
♯P - NP問題の解を数える問題
♯P完全 - ♯P の中で最も難しい問題群
AH - 算術的階層
AP - 交替性チューリングマシンで多項式時間で解ける問題のクラス
BPP - 乱択アルゴリズムで多項式時間で解ける問題のクラス（解はおそらく正しい）
BQP - 量子コンピュータで多項式時間で解ける問題のクラス（解はおそらく正しい）
Co-NP - 非決定性機械で "NO" であることが多項式時間で決定可能な問題のクラス
