1 多項式時間還元の基本概念
1.1 還元の目的と計算困難性の比較
多項式時間還元は、ある問題の解法が別の問題の解法へと利用できる関係を、計算資源の観点から比較する枠組みである。還元の狙いは、元の問題が持つ計算上の「困難さ」を、変換先の問題へ正確に写し取ることにある。ここでいう困難さは、単に実装のしやすさではなく、計算量が入力サイズに対してどの程度増えるかという理論的な尺度で捉える。
還元が成立すると、変換元の問題を直接解く必要がなくなり、代わりに変換先を解くことで全体としても多項式時間に収まる可能性が保証される。したがって、変換先が難しいと考えられるなら、変換元も同等に難しい（少なくともそれに準じる）という主張を体系的に行える。
1.2 多項式時間という制約
還元の変換手続きは多項式時間で実行できる必要がある。これは、「簡単に見える形へこっそり置き換えてしまう」ことを防ぐための制約であり、変換に要するコストが入力サイズに対して許容される範囲に収められることを意味する。多項式時間であれば、入力長が大きくなったときに計算量が指数的に暴発せず、理論上の比較が成立する。
同様に、変換後の解を元の問題の解へ戻す処理も、多項式時間で行えることが重要になる。これにより、還元は単なる「問題の別名化」ではなく、解決可能性や計算困難性を保ったまま情報を受け渡す操作として扱える。
1.3 形式的な定義（写像と計算可能性）
形式化では、問題を入力と出力の対応として表すことが多い。決定問題であれば、入力に対して「条件を満たすか否か」という真偽の出力を考える。還元ではまず、入力を変換する写像が定義され、その写像が多項式時間で計算可能であることが求められる。写像により得られた新しい入力に対して、変換先の問題を解き、その結果を使って元の問題の答えを導く。
この導出も計算可能性の一部として要求され、通常は多項式時間で実行可能な計算規則として表される。写像と復元の両者が多項式時間の枠内にあることで、「効率よく変換して、効率よく元へ戻す」構造が理論的に保証される。
1.4 合成可能性と還元関係の性質
多項式時間還元は、しばしば「合成可能性」を備える。すなわち、問題AからBへ還元でき、さらにBからCへ還元できるなら、AからCへも多項式時間の枠内で還元できるような関係になる。これは還元を推論に使う際の重要な性質である。局所的な変換を積み上げて、最終的な比較へ到達できるため、複雑性クラス間の包含関係や相対的な難しさの順序づけが可能になる。
また、還元関係は反射性や推移性といった性質を持つ形で扱われることが多く、数学的な議論の基盤として整備されている。これにより、「ある問題が別の問題より少なくとも同程度に難しい」という主張を、信頼できる手続きとして積み重ねられる。
2 決定問題に対する還元
2.1 多対1還元（Karp還元）の概要
決定問題同士の還元で代表的なのが多対1還元である。これは、変換元の各入力に対して、変換先の入力を一つだけ計算し、変換先の答えをそのまま（あるいは単純な規則で）変換元の答えへ対応させる枠組みである。多くの教科書ではKarp還元としても知られる。
多対1の特徴は、変換先のオラクル呼び出し回数が入力につき一回に限られる点にある。複数回の呼び出しを許す一般化もあるが、まずはこの整理された形を基礎として関係を組み立てることが多い。
2.1.1 変換関数の条件（多項式時間での計算）
多対1還元では、変換関数が多項式時間で計算可能であることが要件となる。変換関数は、変換元の入力を変換先の入力へ写像する計算手続きとして定義され、入力長の増加に対して実行時間が多項式で抑えられる必要がある。
また、変換先の入力が形式的に定められた言語（決定問題の入力集合）に属するように、変換関数は適切な出力形式を満たすことが前提になる。これにより、理論上の議論が「意味のある問い合わせ」に限定される。
2.1.2 解の対応関係（充足・否定の扱い）
還元が正しくなるためには、変換先の「受理／拒否」の意味が変換元の真偽と整合することが必要である。典型的には、変換元の入力がある性質を満たすなら、変換先の対応する入力も必ず同じ側の答えを返す、という形で対応が定められる。
否定側の扱いも同様に、変換元が満たさないときには変換先も満たさないことが保証される。つまり、変換が作る対応関係は一方向だけでは不十分であり、両方向の整合性によって「同等な可決性」が論証される。
2.2 同値性としての位置づけ
還元は多くの場合、「少なくとも同程度に難しい」という比較として用いられるが、還元の往復が成立する場合にはより強い意味が生じる。具体的には、問題Aが問題Bへ還元でき、かつBがAへ還元できるとき、両者の難しさは相対的に同程度であると見なされる。これにより、問題を複雑性の観点で束ねることが可能になる。
この枠組みは、複雑性クラスの内部でどの問題が代表かを整理するのに役立つ。さらに、どの問題が「基準となる難しさ」を持つかを決める際に、往復還元の考えが自然に使われる。
2.3 代表的な例の作り方（問題の結び替え）
代表的な還元の設計は、「構造の対応」を見つける作業として説明できる。変換元の問題の解が存在することと、変換先の問題の解が存在することが、同じ論理的骨格に基づいて結びつくように、入力の形を組み替える。多くの場合、制約条件や記述言語の差異を埋めるために、変換先の形式に合わせた符号化を導入する。
例としては、論理式の充足性に関する問題を別形式の制約充足へ写し替える、あるいはグラフの性質に関する問題を別種類のグラフ特徴へ落とし込む、といった手順が挙げられる。鍵は、変換が入力サイズに対して過度に増大しないように設計することである。これが、多項式時間の条件と直接結びつく。
3 検索問題・関数問題への拡張
3.1 ランダム化を含む還元の扱い
決定問題では真偽値の整合が中心となるが、検索問題では具体的な対象（witness）を求める必要がある。ここでは解を「見つける」こと自体が要求されるため、還元の考え方もそれに合わせて調整される。また、還元の過程にランダム化を許すモデルが導入されることがある。これは、解の探索を確率的手続きで行い、その成功確率を十分に高く保つ形で意味を与えるためである。
ランダム化還元では、確率的な選択によって変換先の出力から元の解を復元するため、成功条件は「確実」ではなく「高確率」などとして規定される場合が多い。理論的には、確率の扱いが結果の強さを左右するため、定義の細部が重要になる。
3.2 真偽値だけでなく出力を戻す還元
検索問題や関数問題では、変換後の答えが単なる受理／拒否ではなく、何らかの対象を含むことが多い。したがって、還元は変換後の出力を入力として、元の要求する出力へ変換する手続きとして定めるのが自然である。
このとき復元ルーチンは、変換の設計により決まる関数として表現される。変換元の入力から一度変換先の入力を作り、変換先の計算結果を用いて変換元の出力を組み立てる、という構図が基本になる。決定問題よりも情報量が多いため、整合性の要求もより具体的になる。
3.3 多項式時間での復元処理
拡張された還元の要点は、復元処理を多項式時間で実行できるようにする点である。検索や関数の文脈では、復元に計算資源がかかりやすく、設計によっては変換先の情報が十分に扱えない場合もある。そのため、復元は「変換先の出力を効率的に読み取り、必要な形式へ変換する」計算として定義される。
復元が多項式時間であることにより、変換先を解くコストと合わせて、全体としての効率が保証される。結果として、検索・関数問題においても相対的な難しさの比較が成立し、問題間の関係を体系化できる。
4 還元と計算複雑性クラス
4.1 NPと還元の関係（難しさの伝播）
計算複雑性クラスの議論では、還元は「難しさの伝播」を実現する手段として使われる。たとえば、ある問題がNPに属することが示され、さらにその問題が別の問題へ還元できるなら、後者の難しさを前者の観点から評価できる。具体的には、変換元がNPに属する場合、その解証明の検証可能性が還元を通じて保たれることが多い。
さらに、変換先に効率的な解法が存在するなら、変換元にも効率的な解法が構成できる。したがって、「変換先がたとえ未知であっても、解き方が存在しないなら変換元にも存在しない」という方向の論証が組める。この推論の連鎖が、還元を複雑性理論の中心的道具にしている。
4.2 完全性（NP完全・coNP完全など）と還元
完全性は、還元を介して「最も難しい種類」を特徴づける概念である。ある複雑性クラスCに属する問題Xが、Cの任意の問題Yへ還元できるとき、XはCに関して完全であると見なされる。NP完全の場合、NPに属するすべての問題がNP完全問題へ還元できるため、NP完全問題が効率的に解ければNP全体が効率的に解けることになる。
coNP完全も同様に、否定側の性質に関するクラスで定義される。還元の種類（多対1か、別の強さを持つ還元か）によって完全性の基準が変わるため、完全性を主張する際にはどの還元を用いたかが重要になる。これにより、証明の厳密さが担保される。
4.3 証明戦略としての還元の役割
還元は、難しさを示すときの標準的な証明戦略である。典型的には次のような流れになる。まず、既知の完全性または強い下界を持つ問題を出発点とし、それが対象とする問題へ還元できることを示す。これにより、対象の問題が既知の難しさを少なくとも引き継ぐことが結論できる。
この戦略の利点は、対象問題の直接的な性質を解析する代わりに、既知の参照点（基準問題）への接続を示せばよい点にある。証明の工数は変換関数の構成に集中し、論理的な整理を通じて要求事項が明確になる。
4.4 直感的な見取り図（「これが解ければあれも解ける」）
直感としては、「ある問題が解けるなら、それを使って別の問題も解ける」という連鎖を考えると理解しやすい。還元はこの連鎖を形式化したものであり、変換元から変換先へ情報が写ることで、後者の解法が前者へ転用可能になる。
見取り図では、矢印が「変換元が解けることが変換先の解法へつながる」という関係を表すことが多い。実際には、矢印の向きや定義により「どちらがどちらを示すか」が決まるが、核心は「解の利用可能性」を多項式時間の枠内で保証する点にある。こうして複雑性の相対順位が描けるようになり、未解決の問題がどこに位置するかを議論できる。