エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
サヴィッチの定理 - Wikipedia
サヴィッチの定理(英: Savitch's theorem)とは、1970年にウォルター・サヴィッチが証明した計算量理論... サヴィッチの定理(英: Savitch's theorem)とは、1970年にウォルター・サヴィッチが証明した計算量理論における定理である。f(n) ≥ log(n) であるような任意の関数 f について、次が成り立つとするものである。 NSPACE(f(n)) ⊆ DSPACE(f²(n)). 言い換えれば、非決定性チューリング機械が f(n) の領域を使ってある問題を解けるとき、通常の決定性チューリング機械は同じ問題をその平方の領域を使って解ける。時間は非決定性によって指数関数的に短縮されると考えられるが、この定理によれば、領域の効率化は明らかにそれよりも限定的である。 この証明は構築的に行われる。まず、STCON問題(有向グラフの2点間の経路の有無を問う問題)のアルゴリズムとして、n 個のノードからなるグラフについて log2(n) の領域を要する方式を示す。次にこれを用いて、開始ノ