……">

翻訳と辞書 Words near each other ・ 多項式時間 ・ 多項式時間アルゴリズム ・ 多項式時間変換 ・ 多項式時間帰着 ・ 多項式時間近似スキーム ・ 多項式時間還元 ・ 多項式環 ・ 多項式行列 ・ 多項式補間 ・ 多項式関数 ・ 多項式階層 ・ 多頭ノズル噴霧機 ・ 多頭帯 ・ 多頭条虫 ・ 多頻度小口配送 ・ 多額 ・ 多額納税者 ・ 多額納税者議員 ・ 多額納税議員 ・ 多顎 Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク 多項式階層 ： ウィキペディア日本語版 多項式階層[たこうしきかいそう] 多項式階層（たこうしきかいそう、）は、計算量理論における計算量の階層であり、神託機械を使って P、NP、co-NP を一般化させて定義されるものである。 == 定義 == 多項式階層をなすクラス群の定義はいくつか存在する。 多項式階層は神託機械を使って次のように定義する。 ここで、P は多項式時間内で解ける決定問題の集合である。i ≥ 0 については、次のように定義する。 ここで、AB はクラス A のチューリングマシンにクラス B の何らかの問題を解く神託を付加して強化したもので解ける決定問題の集合である。例えば、$\backslash Sigma\_1^\; =\; ,\; \backslash Pi\_1^\; =$ であり、$\backslash Delta\_2^\; =$ は NP に属する何らかの問題を解く神託を備えることで多項式時間で解ける問題のクラスである。 多項式階層の存在/全称的定義のため、$L$ を形式言語（すなわち、一種の決定問題であり、 * の部分集合である）、$p$ を多項式とし、次のように定義する。 ここで、$\backslash langle\; x,w\; \backslash rangle\; \backslash in\; \backslash ^$ * は2進文字列 ''x'' と ''w'' を1つの2進文字列にする何らかの標準的符号化である。''L'' は文字列の順序対の集合を表しており、第一の文字列 ''x'' は $\backslash exists^p\; L$ の元で、第二の文字列 ''w'' は ''x'' が $\backslash exists^p\; L$ の元であることを示す短い ($|w|\; \backslash leq\; p(|x|)$) 証拠である。言い換えれば、$x\; \backslash in\; \backslash exists^p\; L$ は、$\backslash langle\; x,w\; \backslash rangle\; \backslash in\; L$ であるような短い証拠 ''w'' が存在することと同値である。同様に次のように定義する。 ドモルガンの定理により、$\backslash left(\; \backslash exists^p\; L\; \backslash right)^\; =\; \backslash forall^p\; L^$ かつ $\backslash left(\; \backslash forall^p\; L\; \backslash right)^\; =\; \backslash exists^p\; L^$ であり、ここで ''L''c は ''L'' の補集合である。ここで $\backslash mathcal$ を言語のクラスとする。次のように定義することで、これら作用素が言語のクラス群全体に作用するよう拡張する。 再びドモルガンの定理により、$\backslash exists^\; \backslash mathcal\; =\; \backslash forall^\; \backslash mathcal$ かつ $\backslash forall^\; \backslash mathcal\; =\; \backslash exists^\; \backslash mathcal$ であり、ここで $\backslash mathcal\; =\; \backslash left\backslash$ である。クラス NP と co-NP は $=\; \backslash exists^$ と $=\; \backslash forall^$ と定義され、ここで P は（多項式時間で）適切に決定可能な言語群の全体のクラスである。多項式階層は次のように再帰的に定義できる。 なお、$=\; \backslash Sigma\_1^$ であり、かつ $=\; \backslash Pi\_1^$ である。この定義は多項式階層と算術的階層の密接な関連を反映しており、後者で DEC と CE が果たした役割をそれぞれ P と NP が果たしている。同様の方法で、実数の部分集合の階層として解析的階層が定義される。 交替性チューリング機械を使った等価な定義として、$\backslash Sigma\_k^$（あるいは $\backslash Pi\_k^$）は存在的状態（あるいは全称的状態）から開始する交替性チューリング機械で $k$ 回の交替を行うことで多項式時間で解ける決定問題の集合と定義される。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「多項式階層」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.