還元_(計算複雑性理論)

ウィキペディア

還元 (計算複雑性理論)

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

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

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

概要

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

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

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

a × b = ((a + b)² - a² - b²)/2.

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

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

出典は列挙するだけでなく、脚注などを用いてどの記述の情報源であるかを明記してください。 記事の信頼性向上にご協力をお願いいたします。（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日本語例文用例辞書

「還元 (計算複雑性理論)」の例文・使い方・用例・文例

• 酸化還元反応として知られている過程
• 倉庫型量販店が持つ巨大なバイイングパワーは、低価格と節約という形で買い物客へ還元されている。
• 自動車メーカーがしばしばディーラーに対して新車販売用にバックマージン（リベート、キックバック）を付与し、それが最終消費者に「キャッシュバック」として還元される。
• 当社は、安定的な株主還元を経営の重要課題の1つと位置付けている。
• 棚卸資産の評価方法の一つが売価還元法である。
• 弊社は企業文化の活動を通して、社会に還元しています。
• 創業30周年の記念配当を株主様に還元する事をお知らせします。
• ゲイツ会長、広告収入をユーザーに還元する意向表明。
• 化合物が還元する
• 還元剤
• 彼らの人生に対する観点は還元主義で価値が下がる傾向のものだった−R.H.ロービア
• 還元鉱石
• 木柱でそれらをかき回すことによって、溶融金属を還元する
• 物質を加熱して、酸化させるまたは還元する
• ねっすることにより液体状態に還元された
• 還元論の、または、還元論に関する
• 還元主義的な議論
• HMG-CoA還元酵素を抑制することにより血中コレステロール値を下げる薬品
• 可逆性の化学反応で、反応の1つが酸化でその反対が還元であるようなもの
• NADに似ていて、生きた細胞の大部分に存在するが、異なる代謝プロセスに還元剤として役立つコエンザイム