以下の表はいくつかの問題（または文法、言語）のクラスを計算複雑性理論の中で捉えて図示したものである。クラス X が Y の真部分集合である場合、X を Y の下に置き、実線でそれらを接続している。X が部分集合であっても上位と等しい可能性もある場合、破線で接続している。決定可能か決定不能かは、どちらかと言えば計算可能性理論の範疇であるが、ここでは複雑性クラスの関係を示すために入れてある。
以下の一覧の各複雑性クラスには補問題の集合である 'Co' の付くクラスが存在する。例えば、問題 L が NP に含まれるなら、その補問題は Co-NP に属する。
- #P - NP問題の解を数える問題
- #P完全 - #P の中で最も難しい問題群
- AH - 算術的階層
- AP - 交替性チューリングマシンで多項式時間で解ける問題のクラス
- BPP - 乱択アルゴリズムで多項式時間で解ける問題のクラス（解はおそらく正しい）
- BQP - 量子コンピュータで多項式時間で解ける問題のクラス（解はおそらく正しい）
- Co-NP - 非決定性機械で "NO" であることが多項式時間で決定可能な問題のクラス
- Co-NP完全 - Co-NP の中で最も難しい問題群
- DSPACE(f(n)) - 決定性機械で空間計算量 O(f(n)) で解ける問題のクラス
- DTIME(f(n)) - 決定性機械で時間計算量 O(f(n)) で解ける問題のクラス
- E - 線形な指数の指数関数時間で解ける問題のクラス（底を2とするDTIME(2O(n))と等価）
- ESPACE - 線形な指数の指数関数領域で解ける問題のクラス
- EXPSPACE - 指数関数領域で解ける問題のクラス
- EXPTIME - 指数関数時間で解ける問題のクラス
- ELEMENTARY - 指数階層に属す問題のクラス（ループ深度が高々 2 のループプログラムで解ける問題のクラス）
- IP - 対話型証明系で多項式時間で解ける問題のクラス
- L - 対数領域で解ける問題のクラス
- LOGCFL - 文脈自由言語に還元可能な対数領域で解ける問題のクラス
- NC - 並列コンピュータ上で効率的に解ける問題のクラス（O((log n)c）
- NEXPTIME - 非決定性機械で指数関数時間で解ける問題のクラス
- NL - 非決定性チューリングマシンで対数領域で解ける問題のクラス
- NP - 非決定性チューリングマシンで多項式時間で解ける問題のクラス（P≠NP予想も参照）。これはまた解に対して多項式長の witness が存在し、解の候補と witness が与えられたとき検証が決定性チューリングマシンで多項式時間で解ける問題のクラスに一致する
- NP完全 - NP の中で最も難しい問題のクラス
- NP困難 - NP完全かそれより難しい問題のクラス
- NSPACE(f(n)) - 非決定性機械で空間計算量 O(f(n)) で解ける問題のクラス
- NTIME(f(n)) - 非決定性機械で時間計算量 O(f(n)) で解ける問題のクラス
- P - 多項式時間で解ける問題のクラス
- P完全 - P の中で最も難しい問題のクラスであり、並列コンピュータで解ける
- PH - 多項式階層にあるクラス群の和集合
- PP - 確率的に多項式時間で解ける問題のクラス（解が正しい可能性は2分の1より若干大きい)
- PR - 原始再帰関数で解ける問題のクラス
- PSPACE - 多項式領域で解ける問題のクラス
- PSPACE完全 - PSPACE の中で最も難しい問題群
- R - 有限時間で解ける問題のクラス。つまり、チューリングマシンで解ける全問題の集合であり、帰納言語に相当
- RE - "YES" ならば停止し、"NO" ならば停止しないチューリングマシンの存在する問題のクラス。すなわち、帰納的可算言語に相当。これはまた解に対して witness が存在し、解の候補と witness が与えられたとき検証がチューリングマシンで解ける問題のクラスに一致する
- RP - 乱択アルゴリズムで多項式時間で解ける問題のクラス（解がNOの場合は正しくない可能性があるが、YESなら正しい）
- UP - 非決定性チューリングマシンで多項式時間で解ける決定問題のクラス（PとNPの中間）
- ZPP - 乱択アルゴリズムで解ける問題のクラス（解は常に正しいが、平均で多項式時間かかる）
