2026-08-25·無料·12分で読めます

NP完全を1から — 「解けない」ではなく「検証は速い」

NPはNon-Polynomialの略ではありません。「答えを見せられたら速く確認できる」というクラスの話です。P vs NP・還元・NP完全を前提知識ゼロから積み上げ、シフト表や配送計画といった現場の問題にそれがどう現れるかまで見ます。

#np-complete #complexity #p-vs-np #reduction #algorithms

数独を思い出してほしい

数独を解くのは骨が折れます。候補を絞って、行き詰まって戻って、をひたすら繰り返す。ところが、誰かが埋め終わった盤面を渡されて「これ合ってる?」と聞かれたら、確認は一瞬です。各行・各列・各ブロックに1から9が1回ずつ入っているか目で追うだけ。

解くのは大変、確かめるのは楽。 この非対称さが、計算量理論でいちばん有名な未解決問題 P vs NP の正体です。

先に誤解を1つ潰します。NP は Non-Polynomial（非多項式）の略ではありません。Nondeterministic Polynomial（非決定性多項式時間）の略で、意味はむしろ逆寄りです。「この問題はNPに属する」は「難しい」ではなく「答えの確認が速い」と言っています。取り違えたまま設計会議で「NPなので無理です」と言うと、技術的に間違ったことを言っていることになります。

P — 多項式時間で解ける問題

入力の大きさを $n$ とします。頂点が $n$ 個のグラフ、要素が $n$ 個のリスト、といった規模のことです。実行時間が $n$ の多項式、つまり $n$ 、 $n\log n$ 、 $n^2$ 、 $n^3$ …… で抑えられる問題の集まりを P と呼びます。ソートも最短経路も素数判定もここに入ります。

なぜ多項式という一見ざっくりした線引きなのか。合成しても壊れないからです。多項式時間の処理の中で別の多項式時間の処理を多項式回呼んでも、全体は多項式時間に収まります。部品を組み合わせても分類が変わらないうえ、命令セットやメモリの違いも多項式の範囲に吸収されるので、「Pに属するか」は特定のCPUではなく問題そのものの性質になります。

もちろん $n^{100}$ は多項式でも実用にはなりません。オーダー記法が何を捨てているかは計算量を1から理解するで扱っています。

NP — 答えを見せられたら速く確認できる

NP は「解ける」ではなく「検証できる」で定義されます。

「はい／いいえ」で答える問題を考えます。「はい」が答えになる入力には、そう主張する証拠（certificate）を添えられるとしましょう。数独なら埋め終わった盤面、「総距離1000km以内で全都市をまわる経路はあるか」なら具体的な巡回順、「この論理式を真にする割り当てはあるか」なら割り当てそのものです。

証拠の長さが入力サイズの多項式以内に収まり、その検証が多項式時間で終わるなら、その問題は NP に属します。

x \in L \iff \exists w \;\big[\, |w| \le p(|x|) \;\wedge\; V(x, w) = 1 \,\big]

(1)

式(1)を日本語に戻します。 $x$ は入力、 $L$ は「答えがはいになる入力の集まり」、 $w$ は証拠、 $p$ は何らかの多項式、 $V$ は多項式時間で動く検証器です。読み下せば「 $x$ の答えがはいであることは、多項式サイズの証拠 $w$ が存在して検証器がそれを受理することと同じ」。証拠を見つける手間はどこにも書かれていない、そこが肝心です。誰かが持ってきた前提で、確認だけを問うています。

$\mathrm{P} \subseteq \mathrm{NP}$ はすぐ分かります。自力で速く解けるなら証拠は空でよく、検証器が自分で解き直せばいい。未解決なのは逆向き、 $\mathrm{P} = \mathrm{NP}$ か? です。クレイ数学研究所が2000年に選んだミレニアム懸賞問題の1つで、賞金は100万ドル。多くの研究者は $\mathrm{P} \ne \mathrm{NP}$ を予想していますが、どちら向きの証明も出ていません。

指数がどれだけ非常識か

「総当たりすれば」が通用しない規模の話をしています。

FIG 1nを動かしながら対数軸に切り替えると、多項式と指数の差が「定数倍」ではなく「桁」であることが見える

50個の要素から部分集合を全部試すと $2^{50} \approx 1.13\times10^{15}$ 通り。仮に1秒で10億通り調べられる計算機でも約13日かかります。100個なら $2^{100} \approx 1.27\times10^{30}$ 通りで、同じ計算機では宇宙の年齢の千倍以上です。

本当に厄介なのはここです。計算機を1000倍速くしても、扱える $n$ は10ほどしか増えません（ $2^{10}=1024$ だから）。ハードウェアの進歩を待つ作戦が原理的に効かない、ほとんど唯一の領域です。

還元 — 問題を別の問題に着せ替える

個々の問題を別々に論じるのではなく、問題どうしを翻訳して比べる道具を入れます。

問題 A の入力を多項式時間で問題 B の入力に変換でき、しかも「変換後の B の答え」がそのまま「元の A の答え」になるとき、A は B に還元できるといい $A \le_p B$ と書きます。

例として、時間割づくりをグラフの彩色に着せ替えます。授業を1つずつ頂点にし、同じ先生・教室・クラスを使う（＝同時に置けない）2授業の間に辺を引き、コマを色とする。すると「隣り合う頂点に同じ色を塗らない」が、そのまま「衝突する2授業を同じ時間に置かない」になります。翻訳の手間は授業数と衝突数に比例するだけなので多項式時間。彩色を速く解けるなら時間割も速く解ける、というわけです。

$\le_p$ が不等号の形なのは偶然ではありません。 $A \le_p B$ は「A は高々 B と同じくらいの難しさ」を意味します。そしてここが最も間違えられる場所です。目の前の問題が難しいと示したいなら、翻訳の向きは「既知の難問 → 自分の問題」でなければなりません。 逆向きを作っても「自分の問題は既知の難問より簡単かもしれない」としか言えず、難しさの証明にはなりません。

NP完全 — NPの中で最も硬い一群

NP完全の定義は2条件です。

その問題自身が NP に属する（答えの検証が速い）
NP に属するあらゆる問題が、その問題に多項式時間で還元できる

2つ目が強烈です。無限にある問題すべてが1つに翻訳できる、と主張しています。そんなものが本当にあるのか——1971年に Stephen Cook が、独立に1973年に Leonid Levin が、SAT（論理式の充足可能性問題）がまさにそれだと示しました。

土台が1つできれば、あとは芋づる式です。SAT から新しい問題への還元を1本示せば、SAT 経由でNP全体がその問題に還元できたことになる。1972年に Richard Karp がこの方法で、クリーク・頂点被覆・グラフ彩色・部分和・ハミルトン閉路など21個の組合せ問題を一気にNP完全と示しました。現場でよく見かける顔ぶれです。

帰結が効きます。NP完全問題のどれか1つに多項式時間アルゴリズムが見つかれば、その瞬間にNP全体が P に落ちます。 逆に、半世紀以上どれ1つ崩せていないことが、 $\mathrm{P} \ne \mathrm{NP}$ を信じる実務家なりの根拠になっています。

NP困難との違い

NP困難は上の条件2だけを満たすもので、条件1（NPに属する）は要りません。だからNP完全はNP困難の一部です。停止問題はNP困難ですが、決定不能なのでNPには属しません。

もう1つ紛らわしいのが決定問題と最適化問題の別です。NP完全は「はい／いいえ」で答える決定問題に使う言葉で、「総距離 $K$ 以下の巡回路は存在するか」はNP完全、「最短の巡回路を求めよ」はNP困難と呼び分けます。現場で頼まれるのはほぼ後者ですが、難しさの議論は前者に置き換えるのが定石です。

「NP完全だ」と分かった後にやること

NP完全だと分かることは諦める理由ではなく、戦略を切り替える合図です。手は4つあります。

1. 既製のソルバに載せる。 SATソルバ、MILP（混合整数計画）ソルバ、CP-SAT（制約プログラミング）ソルバは、最悪ケースこそ指数ですが実データの構造を使い切ります。「NP完全＝手が出ない」ではまったくない。

2. 最適解をあきらめる。 保証付きの近似（距離が三角不等式を満たす巡回セールスマン問題には、最適の1.5倍以内を保証する古典的手法があります）と、保証はないが実用的なヒューリスティックの2種類。後者の使いどころは焼きなましと遺伝的アルゴリズムにまとめてあります。

3. 入力の構造に賭ける。 実データのパラメータが小さければ多項式に落ちることがあります。部分和・ナップサックは目標値 $W$ を使ったDPで $O(nW)$ ですが、 $W$ の値に比例するので「擬似多項式」と呼ばれ、 $W$ が巨大だと破綻します。

4. 問題を定義し直す。 制約を1つ落とすとPに落ちることがあります。SATは1節に変数3個ならNP完全ですが、2個（2-SAT）なら多項式時間です。「この制約、本当に必要ですか」と聞き返すのが最も安上がりな高速化になることがあります。

コードで見る境界

部分和問題（選んだ数の合計をちょうど target にできるか）で、総当たりとDPを並べます。

from itertools import combinations

def subset_sum_bruteforce(nums, target):     # O(2^n)
    for r in range(len(nums) + 1):
        for c in combinations(nums, r):
            if sum(c) == target:
                return True
    return False

def subset_sum_dp(nums, target):             # O(n * target) 擬似多項式
    reachable = [False] * (target + 1)
    reachable[0] = True
    for x in nums:
        for s in range(target, x - 1, -1):   # 各数を1回だけ使う
            reachable[s] |= reachable[s - x]
    return reachable[target]

下のDPが効くのは、覚えるべき部分問題が $target+1$ 個しかないからです。この「表が現実の大きさに収まるか」が、多項式と指数を分ける境目そのものになっています。

FIG 2編集距離のDP表。部分問題が m×n 個しかないから最後まで埋まりきる。NP完全な問題では覚えるべき部分問題の数そのものが指数になり、この表が作れない

表を埋める考え方は動的計画法を1から解説で詳しく扱っています。

現場ではこう使う

誰が、いつ。 バックエンド／最適化のエンジニアが「シフト表を自動で作りたい」「トラック20台の配送順を決めたい」と頼まれたとき。インフラ担当がVMやコンテナの配置（＝ビンパッキング）を詰めるとき。コンパイラ屋がレジスタ割当（＝グラフ彩色）を実装するとき。パッケージマネージャの依存解決を書くとき（多くの実装が内部でSATソルバを使っています）。動作は共通で、「これは既知のNP完全問題のどれかではないか」をまず疑うこと。当てはまるなら、自前の総当たりを書き始める前にソルバへ載せる判断ができます。

触るもの。 OR-Tools の CP-SAT なら、打ち切りは max_time_in_seconds、並列度は num_search_workers、既存解を初期値に渡すウォームスタートは AddHint。MILPソルバなら「最適解との差をどこまで許すか」の relative_mip_gap（Gurobiでは MIPGap）が実運用の主役です。モデルの受け渡しは LP形式・MPS形式。SAT/SMTを直接使うなら Z3 や MiniSat 系。

知らないと事故になる落とし穴。

タイムリミットを設定せずに本番へ出す。 最悪ケースが指数なので、入力が1件大きくなっただけでレイテンシが跳ねます。打ち切り時間と「打ち切ったときに返す実行可能解」は必ずセットで用意すること。
ソルバの返り値ステータスを見ない。 CP-SAT の OPTIMAL / FEASIBLE / INFEASIBLE を区別せず「解が返ってきた」で流すと、最適でない解を最適として報告したり、解が存在しない状況を見逃したりします。
最悪ケースと実データを混同する。 「NP完全なので無理です」は技術的に誤りで、実データはたいてい最悪ケースではありません。ただし逆も同じで、「手元のデータで速かったから大丈夫」も危険です。入力の分布が少しずれるだけで指数側へ落ちます。
制約を1つ足したときに難しさが変わることに気づかない。 2部グラフのマッチングはPですが、3組同時のマッチングはNP完全。最短経路はPですが最長経路はNP困難。「似ているから同じくらいの難しさだろう」は通用しません。仕様変更のたびにクラスを疑い直してください。
近似比の意味を取り違える。 「1.5倍以内」は最悪ケースの保証であって、平均が1.5倍という意味でも「だいたい合っている」の言い換えでもありません。

設計レビューで問われる形。 「この問題がNP完全だと考える根拠は?」——正解は「感覚的に難しいから」ではなく「既知のNP完全問題 X から、自分の問題への多項式時間還元が作れるから」。そしてほぼ必ず「Pに落ちる特殊ケースはあるか」が続きます。両方に答えられると、議論が「諦める／諦めない」から「どう設計を変えるか」へ移ります。

まとめ

P は「解くのが速い」、NP は「答えの確認が速い」。NP は「解けない」の意味ではない
還元は問題の着せ替え。向きが「既知の難問 → 自分の問題」でないと、難しさは何も言えない
NP完全 = NPの中で最も硬い一群。どれか1つが崩れれば全部が崩れる
実務では「解けない」の通告ではなく、「総当たりを書くな。ソルバか、近似か、構造の利用へ」という合図