翻訳と辞書
Words near each other
・ 対数得点法
・ 対数微分
・ 対数微分法
・ 対数方眼紙
・ 対数期
・ 対数正規分布
・ 対数正規則
・ 対数的微分形式
・ 対数積
・ 対数積分
対数空間還元
・ 対数級数則
・ 対数螺旋
・ 対数螺線
・ 対数表
・ 対数関数
・ 対数関数の原始関数の一覧
・ 対数領域帰着
・ 対数領域還元
・ 対敵


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

対数空間還元 : ミニ英和和英辞書
対数空間還元[たいすう]
=====================================
〔語彙分解〕的な部分一致の検索結果は以下の通りです。

: [つい]
 【名詞】 1. pair 2. couple 3. set 
対数 : [たいすう]
 (n) logarithm
: [すう, かず]
  1. (n,n-suf) number 2. figure 
: [そら]
 【名詞】 1. sky 2. the heavens 
空間 : [くうかん]
 【名詞】 1. space 2. room 3. airspace 
: [けん, ま]
 【名詞】 1. space 2. room 3. time 4. pause 
還元 : [かんげん]
  1. (n,vs) resolution 2. reduction 3. return to origins 
: [げん, もと, がん]
  1. (n,n-suf,n-t) (1) origin 2. basis 3. foundation 4. (2) former 

対数空間還元 ( リダイレクト:対数領域還元 ) : ウィキペディア日本語版
対数領域還元[たいすうりょういきかんげん]
対数領域還元(たいすうりょういきかんげん、)は、計算複雑性理論において、決定性チューリング機械対数領域を使って計算可能な還元である。概念的には、入力を一定数のポインタで指すことで、固定の対数領域だけを使用する。そのような機械の構成は多項式的に多数存在するので、対数領域還元は多項式時間還元でもある。
対数領域還元は多項式時間還元よりも弱いと考えられ、P に属する空でなく全体でもない言語は、P に属する別の空でなく全体でない言語に多項式時間還元可能だが、NL に属する言語とL に属する言語(共に P に包含される)との間の対数領域還元は L = NL ではないことを暗に示している。NP完全問題が、対数領域還元と多項式時間還元において異なるかどうかは未解決の問題である。
対数領域還元は P に属する言語について使われることが多く、それが多対一還元なのかチューリング還元なのかは問題とされないことが多い。なぜなら、LSLNLP はチューリング還元において閉じており、チューリング還元を施すことで問題がそれらのクラスに属することを示すことが可能であるからである。しかし、NCP に包含されるが、チューリング還元において閉じていないため、多対一還元を使わなければならない。
多項式時間還元が P やそのサブクラスではあまり意味がないのと同様、対数領域還元も L とそのサブクラスを区別するのには役立たない。L に属するほとんどの問題〔ここで「ほとんど」としたのは、他の問題を多対一還元することができない(チューリング還元は可能)問題(その補問題)が少なくとも1つ存在するためである。その問題とは、全ての入力を受容する問題(補問題は全ての入力を拒否する)である。〕は、対数領域還元の下でL完全である。より弱い還元があったとしても、単に問題を L の真部分集合である言語に先延ばしするだけであるため、実際には使われることはほとんどない。
対数領域還元のためのツールは、L = SL という結果によって大きく拡張されてきた。SL完全問題は、今では対数領域還元のサブルーチンとして利用されている。
== 脚注 ==



抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「対数領域還元」の詳細全文を読む

英語版ウィキペディアに対照対訳語「 Log-space reduction 」があります。




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

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