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