還元可能性と非可算性の次数

還元可能性は、ある問題を別の問題に変換することで問題の困難さを比較するものであり、同程度の困難さを持つ問題をグループ化することで、計算可能な範囲を超えた世界を構造化する非可算性の次数が生まれる。

Definition

ある問題が別の問題に還元されるとは、後者の問題のソルバーにアクセスできるアルゴリズムが前者の問題を解ける場合を指す。互いに還元される問題は非可算性の次数を共有し、これらの次数は相対的なアルゴリズム的困難さを測定する順序を形成する。

Scope

このトピックでは、多対一還元とチューリング還元、決定不能性を証明するための還元の利用、厳密により困難な問題を生成するチューリングジャンプ操作、論理的複雑性によって問題を分類する算術的階層、および中間次数の存在などの次数理論の中心的な結果について扱う。

Core questions

• ある解決不能な問題が別の問題よりも難しいと、どのように言えるのか？
• 還元は、決定不能性を証明するためと、問題を整理するために、どのように使われるのか？
• チューリングジャンプは何を生成し、なぜそれは常に厳密に難しいのか？
• 決定可能な問題と停止問題の間に厳密に位置する問題は存在するのか？

Key theories

還元可能性とチューリングジャンプ

チューリング還元はオラクル計算によって問題を関連付け、問題のジャンプ（それに対する停止を符号化するもの）は常に厳密に困難であり、より困難な問題の無限の階層を生成する。

中間次数の存在

フリードバーグ＝ムチニクの定理は、優先法を用いて、決定不能ではあるが停止問題よりも厳密に簡単な計算可能列挙可能問題を構築することでポストの問題を解決し、次数が豊かな構造を持つことを示した。

Clinical relevance

還元手法は、問題を解決不能であること、あるいは計算複雑性理論において手に負えないことを証明するための日常的な主力ツールである。既知の困難な問題が新しい問題に還元されることを示すことで、その困難さが転移され、これこそが数学および計算機科学全体で決定不能性やNP完全性の結果が確立される方法である。

History

チューリングは1939年にオラクルマシンを導入し、ポストは1944年に非可算性の次数の研究を枠組み化し、中間的な計算可能列挙可能次数が存在するかという問題を提起した。フリードバーグとムチニクは1956年から1957年にかけて独立して、優先法を発明することでこの問題を解決し、これがこの分野の中心的な手法となった。

Key figures

• Emil Post
• Alan Turing
• Richard Friedberg
• Albert Muchnik

Seminal works

• soare2016
• rogers1987

Frequently asked questions

還元とは、直感的にどのようなものですか？

それは、ある問題のソルバーを使って別の問題を解く方法です。問題Aの任意のインスタンスを問題Bのインスタンスに変換し、その答えが一致するようにできるなら、BはAと少なくとも同程度に難しく、Bの解はAの解をもたらします。

停止問題よりも難しい問題はありますか？

はい、無限にあります。停止問題にチューリングジャンプを適用すると、厳密に難しい問題が生成され、この操作を繰り返すことで無限の階層が構築されます。したがって、解決不能性には単一のレベルではなく、無限の次数が存在します。