問題間還元とは（全体像）
問題間還元は、解きたい問題Aを、すでに解き方が分かっている問題Bの形に作り変えて、Bのやり方でAも解いてしまう手法のこと。
身近な例が料理。「焼きそばの作り方」が分からなくても、「パスタの作り方」を知っていれば、麺をゆでて炒めて味つけ、という似た手順に作り変えて解決できる。このように「別の問題のやり方を借りる」のが還元の発想だ。
押さえたいのは、変換には条件があること。作り変える作業そのものが速く（多項式時間で）できる必要がある。変換に時間がかかりすぎると、せっかくBで速く解けても意味がなくなるからだ。
詳しく：A≦pBの向きと用途だけ覚えれば戦える
ここが記事の心臓部。還元でいちばん大事なのが、記号A≦pBの意味だ。
A≦pB の意味
| 項目 | 内容 |
|---|---|
| 読み方 | AはB以下の難しさ |
| 意味 | Aの入力を速くBの入力に作り変え、Bが解ければAも解ける |
| 向きの注意 | 「A≦B」はAが簡単という意味ではなく、AはB以下（同等か、より易しい）ということ |
ここを取り違えやすい。A≦pBは「Bが解ければAも解ける」という関係で、AがBより難しくないことを表す。「Aが簡単」と単純に読まないのがコツだ。
この還元が活躍するのが、問題の難しさの証明だ。
還元の主な使いみち
| 用途 | やること |
|---|---|
| NP困難の証明 | すでにNP完全と分かった問題を、対象の問題に還元する |
| アルゴリズムの再利用 | 既知の問題に作り変えて、その解き方を借りる |
つまり、「すでに難しいと分かっている問題を、対象の問題に作り変えられれば、対象も同じくらい難しい」と言える。これがNP困難を証明する定番の方法、というわけだね。
わかりやすく言い換えると
要するに、問題間還元は「別の問題のやり方を借りて解く」やり方だ。
①還元 … 問題Aを問題Bに作り変えて、Bのやり方で解く（焼きそばをパスタの手順で）
②A≦pB … AはB以下の難しさ。Bが解ければAも解ける（向きに注意）
③用途 … 「この問題は既知の難問と同じくらい難しい」と証明できる
「Aが簡単」ではなく「AはBより難しくない」と読むのがコツ。
試験のツボ
🔴 一番出る：AをBに作り変えて解く
①問題Aを問題Bに変換し、Bの解き方でAも解く
②変換そのものは速く（多項式時間で）できる必要がある
🔴 次に出る：A≦pBの向き
①「AはB以下の難しさ」を表す
②Bが解ければAも解ける（「Aが簡単」ではない）
🟡 押さえると安定：用途
①NP困難の証明に使う（既知の難問を対象に還元）
②既知の問題に帰着してアルゴリズムを再利用する
よくある間違い
①「A≦pBはAが簡単という意味」→ ✗ AはB以下の難しさ（同等か易しい）という意味。Bが解ければAも解ける。
②「還元は変換しさえすればよく、速さは関係ない」→ ✗ 変換そのものが速く（多項式時間で）できる必要がある。
③「還元はアルゴリズム設計とは無関係」→ ✗ 既知の問題に帰着して解き方を借りる、設計の道具でもある。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（還元の考え方）
問題間還元の考え方に関する次の記述のうち、正しいものはどれか。
- 還元とは、問題をいっさい変換せず、まったく別の答えをそのまま書き写すことだ
- 還元とは、問題を解くのをあきらめて、近い答えだけを返すための手法のことだ
- 還元とは、問題Aを問題Bに作り変えて、Bの解き方を使ってAも解くことである
- 還元とは、二つの問題をただ並べて、難しさを見た目で比べるだけの操作とされる
解答は 3 だよ。
還元は問題Aを問題Bに作り変えて、Bの解き方を使ってAも解くことなんだ。焼きそばをパスタの手順で作るイメージだよ。
選択肢1の「書き写す」、選択肢2の「あきらめる」、選択肢4の「見た目で比べる」はどれも誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 問題を作り変える |
| 2 | ✗ | あきらめではない |
| 3 | ✓ | AをBに変換して解く |
| 4 | ✗ | 変換して解く手法 |
オリジナル問題2（A≦pBの意味）
A≦pBという記号の意味に関する次の記述のうち、正しいものはどれか。
- A≦pBは、Aが必ず簡単な問題で、Bとはなんの関係もないことを表す記号だ
- A≦pBは、AはB以下の難しさで、Bが解ければAも解けることを表す記号である
- A≦pBは、AがBより必ず難しく、Bを解いてもAは解けないことを表すものとされる
- A≦pBは、AとBがまったく同じ問題であることだけを表す記号のことだ
解答は 2 だよ。
A≦pBは「AはB以下の難しさで、Bが解ければAも解ける」という意味なんだ。「Aが簡単」と単純に読まないのがコツだよ。
選択肢1の「関係がない」、選択肢3の「AがBより難しい」、選択肢4の「同じ問題」はどれも誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | BとのつながりでAを表す |
| 2 | ✓ | AはB以下・Bが解ければAも |
| 3 | ✗ | 向きが逆 |
| 4 | ✗ | 同じ問題という意味ではない |
オリジナル問題3（還元の用途）
問題間還元の用途に関する次の記述のうち、正しいものはどれか。
- 還元は、既知の難問を対象の問題に作り変えてNP困難の証明などに使われる
- 還元は、問題の難しさとは無関係で、計算機科学ではいっさい使われていない
- 還元は変換に時間がいくらかかってもよく、速さは結果に関係しないものとされる
- 還元は、難しい問題を必ず簡単な問題に変えて、誰でも解けるようにする魔法だ
解答は 1 だよ。
還元は既知の難問を対象の問題に作り変えて、NP困難の証明などに使うんだ。「この問題は既知の難問と同じくらい難しい」と言えるようになるよ。
選択肢2の「使われない」、選択肢3の「速さは関係ない」、選択肢4の「必ず簡単にする魔法」はどれも誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | NP困難の証明などに使う |
| 2 | ✗ | 難しさの証明に使う |
| 3 | ✗ | 変換は速くできる必要がある |
| 4 | ✗ | 簡単にする魔法ではない |
まとめ
押さえどころ
- 🔴 還元の考え方 ＝ 問題Aを問題Bに作り変えて、Bの解き方でAも解く。変換は速くできる必要がある。
- 🔴 A≦pBの向き ＝ AはB以下の難しさ。Bが解ければAも解ける（「Aが簡単」ではない）。
- 🟡 用途 ＝ 既知の難問を対象に還元してNP困難を証明。アルゴリズムの再利用にも使う。
次に学ぶ
執筆: SikakuQuest編集部