翻訳と辞書
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-adv,n) (1) time 2. hour 3. (2) occasion 4. moment 
時間 : [じかん]
  1. (n-adv,n) time 
: [けん, ま]
 【名詞】 1. space 2. room 3. time 4. pause 
帰着 : [きちゃく]
  1. (n,vs) return 2. conclusion
: [ちゃく]
  1. (n,suf) (1) counter for suits of clothing 2. (2) arriving at .. 

多項式時間帰着 ( リダイレクト:多項式時間変換 ) : ウィキペディア日本語版
多項式時間変換[たこうしきじかんへんかん]
多項式時間変換(たこうしきじかんへんかん、polynomial-time reduction)は計算量理論の一概念である。多項式時間帰着(たこうしきじかんきちゃく)、多項式時間還元(たこうしきじかんかんげん)ともいう。幾つか種類があるが、内容的に多対一還元であれば、「多項式時間多対一還元」「Karp 還元」などとも呼ばれる。もし内容がチューリング還元であれば、「多項式時間チューリング還元」「Cook 還元」などと呼ばれる。
== 概要 ==
ある問題 A の各問題例を、別の問題 B の問題例に決定性チューリングマシンを用いて多項式時間で変換して答が同じにできるとき、「A は B に多項式時間変換可能である」といい、 A \leq_p B と書く。
ただしここでの変換は A の入力内容に依存してはならない。つまり A という問題の全パターンが B に変換できなければいけない。
この概念は計算理論において問題の「難しさ」の度合いを測る上でよく使われる。
A が B に多項式時間還元可能である場合、B を解くアルゴリズムがあれば、それを応用して A も解ける(この逆は成り立たない)。つまり B は A と同等かそれより難しいと結論できる。また、A \leq_p B かつ B \leq_p A である場合、A と B は多項式時間同値であると言い、A \equiv_p B と書く。このとき A と B は同等の難しさを持つ。
多項式時間還元は重要で広く使われている。何故なら重要な問題同士を互いに変換できる程度には強力で、かつ、NPまたはco-NPに属する問題を P に属する問題に還元することはできそうにない程度には非力だからである。NP完全PSPACE完全EXPTIME完全などの標準的な定義には、この還元可能性の概念を用いることが多い。
しかしながら、多項式時間還元はクラス P の中で用いるには不適当である。何故なら P に属する如何なる問題も、P に属する他の殆ど全ての問題〔ここで「殆ど全て」というのは、他から多対一還元できない例外的な問題があるため(但しチューリング還元はできる)。その問題とは、如何なる入力でも肯定する問題と、同じく否定する問題である。これらを指して「自明な問題」と呼ぶ場合がある。〕に(多対一還元でもチューリング還元でも)多項式時間帰着できるからである。従って、P の中に存在するクラス(例えばNLNC や P 自身)については、代わりに対数領域還元が用いられる。

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

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




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

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