複雑性クラスとは? わかりやすく解説

複雑性クラス

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/08/17 10:08 UTC 版)

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

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

例えば、クラスNP非決定性チューリングマシン多項式時間で解く事が出来る決定問題の集合である。また、クラスPSPACEチューリングマシンで多項式領域で解く事が出来る決定問題の集合である。ここで、領域とは、実世界ではメモリ空間[1]、チューリングマシンではテープの長さと考えればよい。一部の複雑性クラスは函数問題の集合である(例えばFP)。

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

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

複雑性クラス間の関係

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

決定問題
Type 0 (帰納的可算)
決定不能
決定可能
EXPSPACE
EXPTIME
PSPACE
Type 1 (文脈依存)
PSPACE完全
Co-NP
NP
BPP
BQP
NP完全
P
NC
P完全
Type 2 (文脈自由)
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 - 線形な指数の指数関数時間で解ける問題のクラス(底を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 - 乱択アルゴリズムで解ける問題のクラス(解は常に正しいが、平均で多項式時間かかる)

脚注

  1. ^ Optimal Reliability Modeling: Principles and Applications Kuo, Way; Zuo, Ming J. (2003), John Wiley & Sons, p. 62

参考文献

  • Complexity Zoo - 500以上の複雑性クラスとその特性のリスト
  • A diagram of the world of computability and complexity 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完全問題についての教科書的書籍

複雑性クラス

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2009/10/30 11:39 UTC 版)

回路計算量」の記事における「複雑性クラス」の解説

回路計算量の複雑性クラスの多くクラス群の階層定義されている。任意の整数 i について、NCiというクラス存在し深さ O(logi(n)) で入力端子数の制限された AND/OR/NOTゲート使った多項式サイズ回路属している。これらのクラス総称して NC クラスと呼ぶ。入力端子数が無制限ゲートに関しては、ACi とその総称としてAC クラスがある。ゲート数や深さが同じでも、使用するゲート異なれば回路計算量の複雑性クラスも異なる。

※この「複雑性クラス」の解説は、「回路計算量」の解説の一部です。
「複雑性クラス」を含む「回路計算量」の記事については、「回路計算量」の概要を参照ください。

ウィキペディア小見出し辞書の「複雑性クラス」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「複雑性クラス」の関連用語

複雑性クラスのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



複雑性クラスのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの複雑性クラス (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaの回路計算量 (改訂履歴)、ブラムの公理 (改訂履歴)、計算複雑性理論 (改訂履歴)、ラスベガス法 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS