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

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

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

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

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/03/03 07:41 UTC 版)

「ブラムの公理」の記事における「複雑性クラス」の解説

全域計算可能関数 f {\displaystyle f} に対して複雑性クラス C ( f ) {\displaystyle C(f)} と C 0 ( f ) {\displaystyle C^{0}(f)} が次のように定義される C ( f ) := { φ i ∈ P ( 1 ) | ∀ x .   Φ i ( x ) ≤ f ( x ) } {\displaystyle C(f):=\{\varphi _{i}\in \mathbf {P} ^{(1)}|\forall x.\ \Phi _{i}(x)\leq f(x)\}} C 0 ( f ) := { h ∈ C ( f ) | c o d o m ( h ) ⊆ { 0 , 1 } } {\displaystyle C^{0}(f):=\{h\in C(f)|\mathrm {codom} (h)\subseteq \{0,1\}\}} C ( f ) {\displaystyle C(f)} は複雑性が f {\displaystyle f} 以下である全ての計算可能関数からなる集合である。 C 0 ( f ) {\displaystyle C^{0}(f)} は複雑性が f {\displaystyle f} 以下である全てのブール値関数からなる集合である。もしこれらの関数を集合の指示関数と見做すならば、 C 0 ( f ) {\displaystyle C^{0}(f)} は集合の複雑性クラスと考えられる。

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/01 20:32 UTC 版)

「計算複雑性理論」の記事における「複雑性クラス」の解説

ある量の計算資源を使って解くことができるすべての計算問題の集合を複雑性クラスという。 複雑性クラス P は、チューリング機械で多項式時間で解ける決定問題の集合である。このクラスは、直感的に言えば最悪の場合でも効率的に解くことができる問題である。 複雑性クラス NP は、非決定性チューリング機械で多項式時間で解ける決定問題の集合である。このクラスには効率的に解くことが望ましいとされる様々な問題が含まれている。例えば、充足可能性問題、ハミルトン閉路問題、頂点被覆問題などである。このクラスの全問題は、その解法を効率的に検証する方法があるという特徴を持つ。 多くの複雑性クラスは、それを表現するのに必要となる論理体系によって特徴付けられる。これは、記述計算量の概念と関係がある。 各クラスに対し、そのクラスの完全問題を考えることがある。クラスCの完全問題とはCに属する問題のうちで最も計算するのが難しい問題のことである。具体的な定義は以下のようになる。 —困難 (英: — hard) クラスCに対して、問題PがC困難であるとは、Cに属する任意の問題をPに帰着（多くの場合多項式時間帰着を考えるが、そうでない場合もある）できるということである。すなわちPはCに属するいかなる問題よりも、同等かそれ以上に難しいということである。ただし、C完全と異なり、P自身はCに属するとは限らない。 —完全 (英: — complete) クラスCに対して、問題PがC完全であるとは、PがCに属しかつC困難ということである。すなわちPはCに属する問題の中で、本質的に最も難しい問題であるということである。

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/11/14 08:46 UTC 版)

「ラスベガス法」の記事における「複雑性クラス」の解説

平均実行時間が多項式時間となるラスベガス法をもつ決定問題の複雑性クラスを ZPP と呼ぶ。 次のような性質がある。 Z P P = R P ∩ co- R P . {\displaystyle \mathbf {ZPP} =\mathbf {RP} \cap {\text{co-}}\mathbf {RP} .} これは、ラスベガス法に属するアルゴリズムを構築する方法と密接に関係している。RPクラスは、多項式時間の乱択アルゴリズムがある決定問題のクラスであり、解が「no」であるときは常に正しいが、解が「yes」であるときは間違っている可能性がある。そのようなアルゴリズムが、ある問題とその補問題（「yes」と「no」が逆転した問題）について存在するとき、その2つのアルゴリズムを同時にかつ繰り返し実行するとする。すると、最終的にどちらかで間違いのない解が得られる。これが多項式時間を期待できるラスベガス法のアルゴリズムを構築する標準的な方法である。ラスベガス法には最悪実行時間の上限が存在しないことに注意されたい。

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