複雑性クラス

複雑性クラス（ふくざつせいクラス、英: Complexity class）は、計算複雑性理論において関連する複雑性の問題の集合を指す。典型的な複雑性クラスは以下のように定義される。 抽象機械 M によりO(f(n))の計算資源 R を使って解く事が出来る問題の集合（nは入力長） 例えば、クラスNPは非決定性チューリングマシンで多項式時間で解く事が出来る決定問題の集合である。また、クラスPSPACEはチューリングマシンでで解く事が出来る決定問題の集合である。ここで、領域とは、実世界ではメモリ空間、チューリングマシンではテープの長さと考えればよい。一部の複雑性クラスは函数問題の集合である（例えば）。 数理論理学では表現の必要に応じて多数の複雑性クラスが定義される（記述計算量）。 ブラムの公理を使うと、完全な計算模型を参照しなくとも複雑性クラスを定義できる。