翻訳と辞書 Words near each other ・ サヴァ・サヴォフ ・ サヴァール ・ サヴァ川 ・ サヴィアーノ ・ サヴィオ ・ サヴィオ・ヌセレコ ・ サヴィオ・ボルトリーニ・ピメンテウ ・ サヴィオーレ・デッラダメッロ ・ サヴィッジジーニアス ・ サヴィッジ・ジーニアス ・ サヴィッチの定理 ・ サヴィトリ ・ サヴィナ・ヤナトゥ ・ サヴィニ ・ サヴィニャーノ・イルピーノ ・ サヴィニャーノ・スル・パーナロ ・ サヴィニャーノ・スル・ルビコーネ ・ サヴィニョーネ ・ サヴィニ・レ・ボーヌ ・ サヴィニー Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク サヴィッチの定理 ： ウィキペディア日本語版 サヴィッチの定理[さう゛ぃっちのていり] サヴィッチの定理（英: Savitch's theorem）とは、1970年にウォルター・サヴィッチが証明した計算量理論における定理である。''f''(''n'') ≥ log(''n'') であるような任意の関数 ''f'' について、次が成り立つとするものである。 :NSPACE(f(n)) ⊆ DSPACE(f²(n)). 言い換えれば、非決定性チューリング機械が ''f''(''n'') の領域を使ってある問題を解けるとき、通常の決定性チューリング機械は同じ問題をその平方の領域を使って解ける。時間は非決定性によって指数関数的に短縮されると考えられるが、この定理によれば、領域の効率化は明らかにそれよりも限定的である。 == 証明 == この証明は構築的に行われる。まず、STCON問題（有向グラフの2点間の経路の有無を問う問題）のアルゴリズムとして、''n'' 個のノードからなるグラフについて log2(''n'') の領域を要する方式を示す。次にこれを用いて、開始ノードから受容ノードまでの経路があるかどうかを決定する非決定性機械の計算機（非決定性チューリング機械の計算経路からなる木構造）に対応したアルゴリズムを実行する決定性機械を構築する。STCON問題はNL完全なので、以上から NL に属する全問題が L2 に属することが示される。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「サヴィッチの定理」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.