還元 (計算複雑性理論)とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > 還元 (計算複雑性理論)の意味・解説 

還元 (計算複雑性理論)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2025/06/03 06:10 UTC 版)

還元(かんげん、Reduction)とは、計算可能性理論計算複雑性理論において、ある問題を別の問題に変換することを意味する。帰着変換などとも呼ばれる。変換の仕方によっては、問題の複雑性クラスを定義するのに使われる。

直観的に、問題 A が問題 B に還元されるとき、B の解法によって A の答えも得られる。従って A を解くことは B を解くよりも困難ではない。これを A ≤ B のように表記し、≤ に添え字をつけて還元の種類を示す。

概要

過去に解いたことのある問題によく似た問題に出会うことは珍しくない。そのような場合、その新しい問題を素早く解くには、新しい問題を過去の問題に変換して既知の解法で解くのがよいだろう。そして、逆変換することで最終的な答えが得られる。これは還元の最も分かり易い例である。

また、やや複雑な使用法だが、解くのが難しいことが分かっている問題があり、それとよく似た問題を与えられたとする。その新たな問題も同様に難しいのではないかと考えることだろう。ここで逆説的にその新しい問題は簡単に解けると仮定する。その上で過去の問題を新たな問題に簡単に変換(還元)することができたとすると矛盾が生じる。つまり、新たな問題も難しいということが分かるのである。

還元の非常に簡単な例を示す。それは「乗算」から「平方(二乗)」への還元である。我々が加算、減算、平方、2での除算しか知らないとする。その知識だけから、以下の方程式を使うと、任意の2つの数の積を得ることができる:

a × b = ((a + b)2 - a2 - b2)/2.

逆方向の還元も可能である。乗算を知っているなら平方を計算するのはたやすい。つまり、この2つの問題の複雑性は等しいことがわかる。このような還元はチューリング還元に関係する。

しかし、例えば平方は最後に1回しかできないといった制限を加えられると還元が難しくなる。この場合たとえ乗算を含めた基本的演算を全て使用できたとしても(最後に二乗するなら)還元は不可能である。というのも有理数から

出典は列挙するだけでなく、脚注などを用いてどの記述の情報源であるかを明記してください。 記事の信頼性向上にご協力をお願いいたします。2023年10月
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, MIT Press, 2001, ISBN 978-0-262-03293-3
  • Hartley Rogers, Jr.: Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967, ISBN 978-0262680523.
  • Peter Bürgisser: Completeness and Reduction in Algebraic Complexity Theory, Springer, 2000, ISBN 978-3540667520.
  • E.R. Griffor: Handbook of Computability Theory, North Holland, 1999, ISBN 978-0444898821.

関連項目



このページでは「ウィキペディア」から還元 (計算複雑性理論)を検索した結果を表示しています。
Weblioに収録されているすべての辞書から還元 (計算複雑性理論)を検索する場合は、下記のリンクをクリックしてください。
 全ての辞書から還元 (計算複雑性理論) を検索

英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「還元 (計算複雑性理論)」の関連用語

還元 (計算複雑性理論)のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



還元 (計算複雑性理論)のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの還元 (計算複雑性理論) (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS