……"> 多項式階層 について
翻訳と辞書
Words near each other
・ 多項式時間
・ 多項式時間アルゴリズム
・ 多項式時間変換
・ 多項式時間帰着
・ 多項式時間近似スキーム
・ 多項式時間還元
・ 多項式環
・ 多項式行列
・ 多項式補間
・ 多項式関数
多項式階層
・ 多頭ノズル噴霧機
・ 多頭帯
・ 多頭条虫
・ 多頻度小口配送
・ 多額
・ 多額納税者
・ 多額納税者議員
・ 多額納税議員
・ 多顎


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

多項式階層 : ミニ英和和英辞書
多項式階層[たこうしきかいそう]
=====================================
〔語彙分解〕的な部分一致の検索結果は以下の通りです。

: [た]
  1. (n,pref) multi- 
多項式 : [たこうしき]
 (n) polynomial
: [しき]
  1. (n,n-suf) (1) equation 2. formula 3. expression 4. (2) ceremony 5. (3) style 
: [かい]
  1. (n,n-suf) -floor (counter) 2. stories 3. storeys 
階層 : [かいそう]
 【名詞】 1. class 2. level 3. stratum 4. layer 5. hierarchy 

多項式階層 : ウィキペディア日本語版
多項式階層[たこうしきかいそう]
多項式階層(たこうしきかいそう、)は、計算量理論における計算量の階層であり、神託機械を使って PNPco-NP を一般化させて定義されるものである。
== 定義 ==
多項式階層をなすクラス群の定義はいくつか存在する。


  1. 多項式階層は神託機械を使って次のように定義する。
    ここで、P多項式時間内で解ける決定問題の集合である。i ≥ 0 については、次のように定義する。
    ここで、AB はクラス A のチューリングマシンにクラス B の何らかの問題を解く神託を付加して強化したもので解ける決定問題の集合である。例えば、 \Sigma_1^ = , \Pi_1^ = であり、 \Delta_2^ = NP に属する何らかの問題を解く神託を備えることで多項式時間で解ける問題のクラスである。

  2. 多項式階層の存在/全称的定義のため、L形式言語(すなわち、一種の決定問題であり、
    *
    の部分集合である)、p多項式とし、次のように定義する。
    ここで、\langle x,w \rangle \in \^
    * は2進文字列 ''x'' と ''w'' を1つの2進文字列にする何らかの標準的符号化である。''L'' は文字列の順序対の集合を表しており、第一の文字列 ''x'' は \exists^p L の元で、第二の文字列 ''w'' は ''x'' が \exists^p L の元であることを示す短い (|w| \leq p(|x|) ) 証拠である。言い換えれば、x \in \exists^p L は、 \langle x,w \rangle \in L であるような短い証拠 ''w'' が存在することと同値である。同様に次のように定義する。
    ドモルガンの定理により、 \left( \exists^p L \right)^ = \forall^p L^ かつ \left( \forall^p L \right)^ = \exists^p L^ であり、ここで ''L''c は ''L'' の補集合である。ここで \mathcal を言語のクラスとする。次のように定義することで、これら作用素が言語のクラス群全体に作用するよう拡張する。
    再びドモルガンの定理により、 \exists^ \mathcal = \forall^ \mathcal かつ \forall^ \mathcal = \exists^ \mathcal であり、ここで \mathcal = \left\ である。クラス NPco-NP = \exists^ = \forall^ と定義され、ここで P は(多項式時間で)適切に決定可能な言語群の全体のクラスである。多項式階層は次のように再帰的に定義できる。
    なお、 = \Sigma_1^ であり、かつ = \Pi_1^ である。この定義は多項式階層と算術的階層の密接な関連を反映しており、後者で DECCE が果たした役割をそれぞれ PNP が果たしている。同様の方法で、実数の部分集合の階層として解析的階層が定義される。

  3. 交替性チューリング機械を使った等価な定義として、\Sigma_k^(あるいは \Pi_k^)は存在的状態(あるいは全称的状態)から開始する交替性チューリング機械で k 回の交替を行うことで多項式時間で解ける決定問題の集合と定義される。



抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「多項式階層」の詳細全文を読む




スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.