複雑性クラス

提供: miniwiki
移動先:案内検索

複雑性クラス(ふくざつせいクラス、: Complexity class)は、計算複雑性理論において関連する複雑性の問題の集合を指す。典型的な複雑性クラスは以下のように定義される。

抽象機械 M によりO(f(n))の計算資源 R を使って解く事が出来る問題の集合(nは入力長)

例えば、クラスNP非決定性チューリングマシン多項式時間で解く事が出来る決定問題の集合である。また、クラスPSPACEチューリングマシン多項式領域で解く事が出来る決定問題の集合である。一部の複雑性クラスは函数問題の集合である(例えばFP)。

数理論理学では表現の必要に応じて多数の複雑性クラスが定義される(記述計算量)。

ブラムの公理を使うと、完全な計算模型を参照しなくとも複雑性クラスを定義できる。

複雑性クラス間の関係

以下の表はいくつかの問題(または文法、言語)のクラスを計算複雑性理論の中で捉えて図示したものである。クラス XY真部分集合である場合、XY の下に置き、実線でそれらを接続している。X が部分集合であっても上位と等しい可能性もある場合、破線で接続している。決定可能か決定不能かは、どちらかと言えば計算可能性理論の範疇であるが、ここでは複雑性クラスの関係を示すために入れてある。

決定問題
ファイル:SolidLine.png ファイル:SolidLine.png
Type 0 (帰納的可算)
決定不能
ファイル:SolidLine.png
決定可能
ファイル:SolidLine.png
EXPSPACE
ファイル:DottedLine.png
EXPTIME
ファイル:DottedLine.png
PSPACE
ファイル:SolidLine.png ファイル:SolidLine.png ファイル:DottedLine.png ファイル:DottedLine.png ファイル:DottedLine.png ファイル:DottedLine.png
Type 1 (文脈依存)
ファイル:SolidLine.png ファイル:DottedLine.png ファイル:DottedLine.png ファイル:DottedLine.png
PSPACE完全
ファイル:SolidLine.png ファイル:SolidLine.png ファイル:DottedLine.png ファイル:DottedLine.png ファイル:DottedLine.png
ファイル:SolidLine.png ファイル:SolidLine.png
Co-NP
ファイル:DottedLine.png ファイル:DottedLine.png
NP
ファイル:SolidLine.png ファイル:SolidLine.png ファイル:DottedLine.png ファイル:DottedLine.png ファイル:DottedLine.png ファイル:DottedLine.png
ファイル:SolidLine.png ファイル:SolidLine.png ファイル:DottedLine.png
BPP
BQP
NP完全
ファイル:SolidLine.png ファイル:SolidLine.png ファイル:DottedLine.png ファイル:DottedLine.png ファイル:DottedLine.png
ファイル:SolidLine.png ファイル:SolidLine.png
P
ファイル:SolidLine.png ファイル:SolidLine.png ファイル:DottedLine.png ファイル:DottedLine.png
ファイル:SolidLine.png
NC
P完全
ファイル:SolidLine.png ファイル:SolidLine.png
Type 2 (文脈自由)
ファイル:SolidLine.png
Type 3 (正規)

複雑性クラス一覧

以下の一覧の各複雑性クラスには補問題の集合である '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 - 線形な指数の指数関数時間で解ける問題のクラス
  • 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 - 乱択アルゴリズムで解ける問題のクラス(解は常に正しいが、平均で多項式時間かかる)

参考文献

  • [1]
  • Complexity Zoo - 400以上の複雑性クラスとその特性のリスト
  • Diagram by Neil Immerman - 複雑性クラスの階層についての図
  • Michael Garey, and David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman & Co., 1979. NP完全問題についての教科書的書籍

テンプレート:複雑性クラス