NP完全・困難のうれしさを分かりやすく

👨‍🦰「あ〜この問題 NP 困難ですね」

そう言われて寝れなくなる夜もありました

🥺「じゃあ結局、解けないってこと…？」
😕「P / NP / NP完全 / NP困難…なにそれ美味しいん…？」

この記事はそんな人達のためにNP困難の嬉しさの流れを掴むための文章です。
巷には厳密な文章とか賢いChatGPTとか沢山あるので、定義よりも概念的に腹落ちすることを目的とした記事になります。

対象読者

• アルゴリズム／計算量の雰囲気は分かる
• でも P・NP・NP完全・NP困難が“何を嬉しくしてくれるか”を知りたい学部生／高校生

1. いったん Yes/No で聞く：判定問題

「最短にしたい」「最大化したい」みたいな最適化問題は直感的です。
ただし P / NP の議論は、基本的に “Yes/No で答えられる問題（判定問題）” を土台に作られています。

たとえば「最短のルートを求める」ではなく、

長さが 100 以下のルートは存在する？

のように Yes/No で答えられる形の問題を前提にP, NPの話はされます。

2. P と NP：「解く」と「採点できる」は別の能力

自力で解ける？ それとも 答えを渡されたら採点できる？

2.1 P：多項式時間で「解ける」判定問題

P はざっくり以下のような集合です。

入力サイズに対して 多項式時間で Yes/No を判定できる問題 の集合

つまり「入力が大きくなっても、現実的な時間で判定できる」問題の集合です。

2.2 NP：証拠（答えの候補）があれば「確かめる」のは速い

対してNP は、直感的には以下の様になります。

Yes だと主張する 証拠（証明書 / certificate） をもらえたら、それが正しいかを多項式時間で検証できる問題の集合

ここで重要なのは、NP は

• 「答えを高速に見つけられる」とは言っていない

という点です。ちなみにPとNPの関係としては常に以下の条件が成り立ちます

• P ⊆ NP（解けるなら、渡された答えも当然検証できる）

たとえば数独はPには入っていなくてNPに入っているものの問題としてイメージがしやすいです。(ちなみにサイズ可変の一般化数独（n×n）はNP完全です)

• 完成した盤面を渡されたら、合っているかのチェックは速い（検証が速い）
• でも白紙から解けと言われると、大変そう（答えを求めるのが大変）

証拠（witness）の長さは「入力サイズに対して多項式長」くらいに収まっている前提です。証拠が天文学的に長いと、読むだけで終わるので…。

2.3 P vs NP：速く採点できるなら、速く解ける？

ここで有名な未解決問題が出ます。

• P = NP なのか？

言い換えると、

• 「速く検証できるなら、速く答えを見つけることもできるの？」

という問いです。

この問題は未解決なので、NP完全の話では 条件付き の言い方になります。

• もし $P \ne NP$ なら、NP完全問題に「万能な多項式時間の厳密解法」は存在しない

まとめ

• NPは「解ける」じゃなくて “答えがあれば採点できる”
• P=NPは「採点できるなら解ける？」という問い

3. 帰着：難しさ（や速さ）を運ぶ「翻訳」

ここから先、NP完全の話を支える“道具”が 帰着 です。

帰着を一言で言うと以下のようになります。

「Aの質問」を「Bの質問」に言い換えて、Bに丸投げする

(ここでは主に多項式時間 many-one 帰着（Karp帰着）を想定します)

3.1 多項式時間帰着 A -> B の意味

A -> B（AをBに多項式時間で帰着できる）とは、次の2点を同時に満たす「翻訳機 $f$」がある、という意味です。

• 速く翻訳できる：Aの入力 $x$ から Bの入力 $f(x)$ を 多項式時間で作れる
• 答えがズレない：$x$ が Yes ⇔ $f(x)$ が Yes

図にすると以下のようになります。

x (Aの入力)
  |  f（速い翻訳）
  v
y = f(x) (Bの入力)
  |  Bを解く
  v
Yes/No

3.2 矢印の向き①：A -> B は「Bが解ければAも解ける」

A -> B は「AをBに丸投げできる」
＝ 「Bが解けるならAも解ける」

つまり、

• もし B が多項式時間で解ける なら、Aも多項式時間で解けます

3.3 矢印の向き②：「Bが難しい」を言いたいなら 難問 -> 調べたい問題

ここが本当に大事です。「Bが難しい（少なくとも簡単ではなさそう）」を示したいときは、

• すでに難しいと知られている問題Aを持ってきて
• A -> B（難しい方 -> 調べたい方） を示します

こうすると、

• 「AをBに丸投げできる」
  → 「もしBが簡単ならAも簡単になってしまう」
  → 「Aが難しい“側”にいるなら、Bも簡単とは言いにくい」

という形で、難しさの下限が運べます。

4. NP困難・NP完全：ごちゃつく原因は「2つの軸」を混ぜるから

NP困難/NP完全が分かりにくくなる一番の原因は、

• 「NPに入るか？」（採点できるか）
• 「NPの難しさが乗るか？」（NPのすべての問題が帰着できるか）

という 別々の話を一気に聞かされるからです。ここを 2つの軸として分けて整理すると、かなりスッキリします。

4.1 2つの軸で整理する

軸A：NPに入るか？

• NP：Yes を主張する「証拠（witness）」があれば、正しいかを多項式時間で検証できる

これは「解ける」ではなく 採点できる という性質でした。

軸B：NPの難しさが全部乗るか？

• NP-hard（NP困難）：NPのすべての問題 A が Hに帰着できる（＝NPの難しさが全部Hに流れ込む）

これは「採点できるか」ではなく帰着による “難しさの下限”の話です。

NP完全 = “NPに入る” ＋ “NP-hard” の両取り
NP困難 = “NP-hard” だけ（NPに入る必要はない）

4.2 NP困難（NP-hard）：「NPの難しさ全部背負ってます」

問題 H が NP-hard とは：

NPのすべての問題 A が Hに帰着できる

つまり、

• H が速く解けたら、NP中の問題が帰着で全部速く解けてしまう
• なので「H を多項式時間で解く」のは（多くの人が信じるように P≠NP なら）難しい

というものです。またNP-hard は最適化問題に対しても使われます。

※ 画像はイメージです

4.3 NP完全（NP-complete）：NPの中の“代表ラスボス”

判定問題 C が NP完全とは、次の2つを両方満たすことです。

• 証拠があれば多項式時間で検証できる
• NPの難しさが全部帰着してくる

つまり、

• NP の中にいるのに、NPの難しさを全部背負っている

という“ラスボス”的なポジションです。

※ 画像はイメージです

4.4 ここが誤解ポイント：「NP完全 = 解けない」ではない（言えること／言えないこと）

NP完全（やNP-hard）が直接教えてくれるのは、“不可能” ではなく 条件付きのラベルです。

言えること

• もし NP完全問題が1つでも多項式時間で解けたら、P=NP になってしまう
  → つまり「正面突破が成功したら世界がひっくり返る」レベルのラベル付け

言えないこと

• 「絶対に多項式時間では解けない」
  → これは P≠NP が未解決なので、現時点では断言できません

5. NP完全(困難)と分かったら何すれば良い？

NP完全(困難) と分かった瞬間に分かるのは、

• 一般形を、厳密に、いつでも速く──を正面から取りに行くのは分が悪いということです（もしそれができたら、P=NP級の大事件になる）

だから NP完全(困難)は、消耗する方向を早めに捨てて、勝てる方向へ舵を切るためのラベル付けです。

5.1 問題の条件を変えよう

NP完全(困難)を見たら、典型的には次のどれかに進むことが多いです。ポイントは “問題設定のどこかを少し緩める / 変える” ことです。
アルゴリズム研究では以下のようなテーマをもとにした研究も多いです。

入力の形を限定する

現実の入力は「何でもあり」ではなく、偏りや構造があることが多いです。

• 木 / 平面グラフ / 二部グラフ
• 距離が三角不等式を満たす、など

この場合は入力の構造の特性を活かすことで多項式時間アルゴリズムを作ったりすることも出来たりします。

小さいパラメータに押し込める（パラメータ化）

入力全体は大きくても、「ここだけ小さいみたいな特徴」がある場合のときです。

• 例：解のサイズ、変更回数、木幅…などを $k$ として$f(k) · n^{O(1)}$（FPT）となるような$k$が小さいときに高速なアルゴリズムを作る

近似アルゴリズム（品質保証つきの“速い解”）

最適解そのものを捨てて、保証付きのより高速なアルゴリズムを作るという方向性です。

• 「最適の○倍以内」「最適との差が○以内」みたいな保証をつけながら最適解よりも高速なアルゴリズムを作る。

問題のサイズを小さくする（前処理・縮約）

解く前に問題サイズを削ってから、厳密解法やパラメータ化に繋げたりもします。

• 明らかに不要な部分を消す
• 強制的に決まる部分を先に確定する
• 等価な小さい問題に落とす（カーネル化）

ヒューリスティック／ソルバ

現実世界では解の保証がなくても、ある程度いい解を求めれれば嬉しいケースはたくさんあります。

あとがき

元々この記事を書こうと思ったモチベーションは「NP完全・困難の嬉しさをまとめた記事ってあんまり無いかも」というところでした。自分の勉強にもなったのでとても楽しかったです！

この辺りの困難性・容易性の話はもっと書けることがあるので、気が向いたらどんどん書こうと思います💪

分からないことや聞きたいことがあったら気軽にコメントしてください！