応用数学と計算数学

計算複雑性理論:PとNP

解くのにかかる時間の増加の仕方で問題を分類し、P=NP かどうかを中心的な問いとする理論。

直観なぜ一部のパズルは確認は簡単でも解くのは難しいのか

数独パズルを一から解くには、可能性を次々と試しながら長い時間がかかることがある。しかし友人が完成したマス目を渡して、それがパズルを解いていると主張するなら、その主張を確認するのは速い：すべての行、列、箱を重複がないか走査するだけでよい。シャッフルされたトランプの束を並べ替えるのはそれとは違う — どんな並べ替え手法でも数回のパスで解くのが速く、確認するのも同じくらい速い。計算複雑性理論は、この日常的な区別 —「解くのが簡単」対単に「解を確認するのが簡単」— を数学的に厳密にし、その区別が本物なのか幻なのかを問う。

すべての頂点をちょうど1回ずつ訪れるサイクル（ハミルトン閉路）が存在するかを問うグラフである。そのようなサイクルを一から見つけるには、頂点の並べ方を数多く探索する必要があるように見えるが、ハイライトされた候補サイクルは一回の走査で確認できる：連続する各頂点対が実際に辺で結ばれているか、そしてすべての頂点がちょうど1回ずつ現れているかを確かめるだけでよい。

中高実行時間の測定：多項式的増加と指数関数的増加

アルゴリズムの実行時間は通常、入力サイズ $n$ の関数として、ビッグO記法を用いて測られる： $T(n) = O(f(n))$ とは、 $n$ が十分大きくなると実行時間が $f(n)$ の定数倍より速く増加しないことを意味する。 $n$ 個の項目からなる未整列のリストを1つずつ探索するには $O(n)$ ステップかかる。整列済みの $n$ 個の項目のリストに対する二分探索は $O(\log n)$ ステップしかかからない。どちらも $n$ に関して多項式的（実際には線形以下または線形）である。対照的に、 $n$ 個の項目のすべての部分集合を試すには $O(2^n)$ ステップかかる — $n$ に関して指数関数的であり、 $n$ が数十を超えると桁違いに遅くなる。

入力サイズ $n$ に応じて異なる増加率がどう変化するか
増加率	$n=10$	$n=20$	$n=50$
$O(n)$	$10$	$20$	$50$
$O(n^2)$	$100$	$400$	$2{,}500$
$O(2^n)$	$1{,}024$	$\approx 1.05\times 10^6$	$\approx 1.13\times 10^{15}$

大学クラス P と NP

定義: クラス P

P（多項式時間）とは、標準的なコンピュータが入力サイズ $n$ に関するある多項式で抑えられた時間 — すなわちある固定定数 $k$ に対して $O(n^k)$ の時間 — で解けるイエス/ノー問題の集合である。ソート、素数判定、グラフの最短経路探索はいずれも P に属する。

定義: クラス NP

NP（非決定性多項式時間）とは、提案された「はい」という答えに、多項式時間で正しさを確認できる証拠（ハミルトン閉路や式を満たす割り当てのような witness）が伴う一方で、一般にそのような証拠を多項式時間で見つける方法は知られていない、そのようなイエス/ノー問題の集合である。P に属するすべての問題は NP にも属する（速く解けるなら、確認も自明に速い）ので $P \subseteq NP$ である。逆の包含が成り立つかどうかが、まさに P 対 NP の問題である。

P = \bigcup_{k \ge 1} \mathrm{TIME}(n^k)

形式的には、言語 $L$ が NP に属するとは、ある多項式 $p$ と多項式時間の検証器 $V$ が存在して、 $x \in L$ であることと、 $|y| \le p(|x|)$ を満たすある証拠 $y$ が存在して $V(x,y)$ が受理することが同値であることをいう。この検証器に基づく定義は、より一般的な「非決定性チューリング機械」の定義と同値であり、実際にはこちらの方が推論しやすいことが多い。

x \in L \iff \exists\, y,\ |y| \le p(|x|),\ V(x,y) = \text{accept}

大学多項式時間帰着とNP完全性

定義: 多項式時間帰着

問題 $A$ が問題 $B$ に多項式時間で帰着するとは、 $A \le_p B$ と書き、多項式時間で計算可能な関数 $f$ が存在して、 $A$ の任意のインスタンス $x$ を $B$ のインスタンス $f(x)$ に変換し、 $x$ が $A$ の「はい」インスタンスであることと $f(x)$ が $B$ の「はい」インスタンスであることが同値であることをいう。直感的には、 $A \le_p B$ は「 $B$ は少なくとも $A$ と同じくらい難しい」ことを意味する： $B$ に対する高速アルゴリズムがあれば、変換してそれを呼び出すことで直ちに $A$ に対する高速アルゴリズムが得られる。

定義: NP完全

問題 $B$ がNP完全であるとは、 $B \in NP$ であり、かつすべての問題 $A \in NP$ が $A \le_p B$ を満たすことをいう。NP完全問題は NP の中で「最も難しい」問題である：そのうちのどれか1つに対する効率的なアルゴリズムは、帰着を通じて NP のすべての問題に対する効率的なアルゴリズムに変換される。

定理: クック・レビンの定理

ブール充足可能性問題（SAT）— 変数 $x_1,\dots,x_m$ からなるブール式が与えられたとき、それを真にする真偽値の割り当てが存在するかを判定する問題 — はNP完全である。

なぜ正しいのか?

SATが明らかにNPに属すること：充足する割り当ては、値を代入するだけで多項式時間で確認できる証拠である。深い部分は、すべてのNP問題がSATに帰着することを示すことである — これは、ブール式が、任意の多項式時間検証器の実行全体を、セルごと、瞬間ごとに段階的に記述できるほど表現力があるためであり、「証拠が存在するか」が「この巨大な式が充足可能か」に変わる。

証明

$A \in NP$ とし、長さ $n$ の入力に対して長さ高々 $n^k$ の証拠と組み合わせて高々 $n^k$ の時間で動作する多項式時間検証器 $V$ を持つとする。長さ $n$ の入力 $x$ を固定し、あるブール式 $\phi_x$ を、あるチェックリー証拠が $V$ を受理させる場合にちょうど充足可能となるように構築する。

未知の証拠 $y$ に対する $(x,y)$ 上の $V$ の計算全体を、タブローとして並べたものを想像する： $n^k \times n^k$ のグリッドで、行 $t$ が時刻 $t$ における検証器のテープ全体の内容とヘッド位置を記録する。（セル、時刻、可能な記号）の組ごとにブール変数を導入し、その時刻にそのセルにどの記号があるかを記録する — グリッドのセル数と時刻の数は多項式個なので、これは多項式個の変数となる。

式 $\phi_x$ は、4つの局所的で容易に確認できる条件を課す節の連言（AND）として構築される：(1) 各時刻において各セルはちょうど1つの記号を持つ；(2) 行 $0$ は固定入力 $x$ と、まだ推測されていない証拠 $y$ 用の空白プレースホルダを正しく符号化する；(3) 連続する2つの時刻にまたがる隣接セルの小さな窓は、 $V$ の遷移規則と整合する（ここで、行 $0$ で自由にしておいた証拠のビットが、計算の残りの部分に影響を与えることができる）；(4) 最終時刻のあるセルが受理状態を記録する。

これらの条件はそれぞれ、小さな固定サイズの変数の近傍しか制約しないので、それぞれ定数個の節に翻訳され、制約すべき近傍は多項式個しかない — したがって $\phi_x$ は多項式サイズであり、 $x$ から多項式時間で計算可能である。構築により、 $\phi_x$ が充足可能であることは、整合的なタブローが存在すること、すなわちある証拠 $y$ が $V(x,y)$ を受理させること、すなわち $x \in A$ であることとちょうど同値である。これは任意の $A \in NP$ に対する帰着 $A \le_p \text{SAT}$ を示しており、上で示した $\text{SAT} \in NP$ と合わせて、SATがNP完全であることを証明する。

定理: 1つのNP完全問題が易しければPとNPは崩壊する

$B$ がNP完全であり、かつ $B \in P$ であるならば、 $P = NP$ である。

なぜ正しいのか?

$B$ がNP完全であることは、すべてのNP問題が多項式時間で $B$ のインスタンスとして書き換えられることを意味する。もし $B$ 自身が多項式時間で解けるなら、書き換えのステップと解くステップを連結することで、元のNP問題も多項式時間で解けることになる — したがって、扱いやすいNP完全問題がたった1つあれば、すべてのNP問題を道連れにしてPまで引きずり下ろす。

証明

$B$ がNP完全であり、 $B$ を時間 $O(n^{k_1})$ で解くアルゴリズムがあるとする。任意の $A \in NP$ を取る； $B$ のNP完全性より $A \le_p B$ であり、これは $A$ のインスタンスを $B$ のインスタンスに写し、イエス/ノーの答えを保つ、時間 $O(n^{k_2})$ で計算可能な帰着関数 $f$ が存在することを意味する。

$A$ に対する長さ $n$ の入力 $x$ について、まず $f(x)$ を計算する：これには時間 $O(n^{k_2})$ かかり、特に出力 $f(x)$ の長さは高々 $O(n^{k_2})$ である（多項式時間アルゴリズムは実行時間より多くの出力を書き出せない）。次に $f(x)$ に対して $B$ の多項式時間アルゴリズムを実行する： $|f(x)| = O(n^{k_2})$ なので、これには時間 $O\big((n^{k_2})^{k_1}\big) = O(n^{k_1 k_2})$ かかる。

全体の実行時間は $O(n^{k_2}) + O(n^{k_1 k_2}) = O(n^{k_1 k_2})$ であり、依然として $n$ に関する多項式である（2つの多項式の合成は多項式である）。帰着の正しさより、 $x$ が $A$ の「はい」インスタンスであることと $f(x)$ が $B$ の「はい」インスタンスであることは同値なので、この組み合わせた手続きは $A$ を多項式時間で正しく判定する。

$A \in NP$ は任意だったので、すべてのNP問題は多項式時間アルゴリズムを持つ、すなわち $NP \subseteq P$ である。常に成り立つ包含 $P \subseteq NP$ と合わせて、 $P = NP$ が得られる。

いくつかの有名な問題の複雑性の状況
問題	既知の状況
リストのソート	P に属する： $O(n\log n)$ 回の比較で十分
素数判定	2002年以降 P に属する（AKSアルゴリズム）
ブール充足可能性（3-SAT）	NP完全（クック・レビン、1971年）
巡回セールスマン問題（決定版）	NP完全
グラフ同型性判定	NP に属する；2015年以降準多項式時間アルゴリズムあり（Babai）；PかNP完全かは未知
整数の素因数分解	NP かつ co-NP に属する；Pに属するかは未知 — RSAの安全性の根拠となる困難性の仮定

大学実世界での応用と具体例

ある問題がNP完全であると認識することには、即座に実用的な価値がある：それは技術者に、正確で常に高速なアルゴリズムを探すのをやめ、代わりにヒューリスティック、近似アルゴリズム、あるいは特殊構造を利用すべきだと教える。これはまた、現代暗号（RSAの安全性は素因数分解が困難であることに依存する）、物流とスケジューリング（車両経路問題、試験時間割）、生命情報学（タンパク質構造予測、配列アラインメントの各種変形）、コンパイラ最適化（レジスタ割り当てはグラフ彩色そのものであり、NP完全である）の基盤にもなっている。

例: 頂点被覆を独立集合に変換する

$5$ 個の頂点 $\{1,2,3,4,5\}$ からなり、辺 $(1,2), (2,3), (3,4), (4,5)$ を持つパスグラフを考える。 $n$ 個の頂点を持つグラフ $G$ がサイズ $k$ の頂点被覆を持つことと、サイズ $n-k$ の独立集合を持つことが同値であるという事実を用い、 $\{1,3,5\}$ がこのグラフの最大独立集合であることが与えられたとき、最小頂点被覆のサイズを求めよ。

解答

まず $\{1,3,5\}$ が本当に独立であることを確認する：辺 $(1,2), (2,3), (3,4), (4,5)$ のいずれも両端点が $\{1,3,5\}$ に含まれることはなく、選ばれたどの2頂点も隣接しないため、サイズ $3$ の有効な独立集合であることが確認できる； $5$ 頂点のパスは互いに隣接しない $4$ 頂点を持つことができない（唯一のパスに沿ってどこかで2頂点が隣接せざるを得ない）ため、これは最大である。

$n=5$ 、独立集合のサイズ $3$ として帰着の公式を適用する：最小頂点被覆のサイズ $= n - 3 = 5 - 3 = 2$ 。

直接確認する：補集合 $\{2,4\}$ が頂点被覆になっているはずである。すべての辺が $\{2,4\}$ に少なくとも1つの端点を持つか確認する：辺 $(1,2)$ は $2$ に接する；辺 $(2,3)$ は $2$ に接する；辺 $(3,4)$ は $4$ に接する；辺 $(4,5)$ は $4$ に接する。4本の辺すべてがわずか $2$ 頂点で被覆され、答えが確認できる。

頂点被覆と独立集合のこの同値性は、上で論じたような多項式時間帰着（実際にはここでは線形時間で計算可能で可逆な、非常に単純な帰着）そのものである：頂点被覆も独立集合もどちらもNP完全な決定問題であり、この帰着は、それらが正確な意味で、2つの異なる角度から見た同じ問題であることを示している。

例: なぜ総当たりは控えめな規模でも失敗するのか

$n$ 個のブール変数を持つ充足可能性問題に対する総当たりアルゴリズムは、可能な真偽値の割り当て $2^n$ 通りをすべて確認し、高速なコンピュータ上で1つの割り当てあたり約 $10^{-9}$ 秒（1ナノ秒）を費やす。 $n=50$ 変数の場合、この総当たり探索が何秒かかるかを、最も近い10のべき乗で見積もれ。

解答

必要な確認回数は $2^{50}$ である。 $2^{10} = 1024 \approx 10^3$ なので、 $2^{50} = (2^{10})^5 \approx (10^3)^5 = 10^{15}$ となる；より正確には $2^{50} \approx 1.1259 \times 10^{15}$ である。

割り当て1つあたりのコスト $10^{-9}$ 秒を掛けると、合計時間はおよそ $1.1259 \times 10^{15} \times 10^{-9} = 1.1259 \times 10^{6}$ 秒となる。

最も近い10のべき乗に丸めると、これは約 $10^{6}$ 秒 — およそ $11$ 日から $13$ 日間の連続計算であり、これはわずか $n=50$ 変数、実応用では小さいとみなされる規模である（産業用のSATインスタンスは日常的に数千から数百万の変数を持つ）。

これこそが、多項式時間と指数関数時間の区別が、理論だけでなく実務においても重要である理由である：仮に、例えば $n^3$ ステップで動く多項式アルゴリズムがあれば、必要なのはわずか $50^3 = 125{,}000$ ステップ — ミリ秒の何分の1か — であり、PとNPの問題がいかに大きな実務上の利害を持つかを示している。

よくある誤り. よくある誤解は、「NP」が「not polynomial（多項式的でない）」の略だというものである — 実際には非決定性多項式時間の略であり、Pに属するすべての問題はNPにも属するので、NPに属することは問題が難しいことを意味しない。2つ目のよくある誤りは、ある程度努力しても高速なアルゴリズムが見つからないこと、あるいは特定のアプローチが失敗することを証明したとしても、それは問題がPの外にあることを証明するわけではないという点である — 誰かがNP完全問題に対する多項式アルゴリズムを見つけるか、そのようなものが存在しないことを証明するまで、

P = NP

は論理的に可能なままである。

研究の最前線 2026年時点

2026年現在、 $P$ 対 $NP$ は未解決のままであり、クレイ数学研究所の7つのミレニアム懸賞問題の1つであり、正しい解決には $1{,}000{,}000$ ドルの賞金がかけられている。進展は直接的な答えというよりも複数の方向から得られている：回路計算量はNP困難問題が指数関数的に大きなブール回路を必要とすることを証明しようとしているが、数十年の努力にもかかわらず、かなり制限された回路モデルに対してさえ超線形の下界は知られておらず、自然証明の障壁（ラズボロフ・ルーディッチ、1994年）は、多くの有望な手法がなぜうまくいかないのかを構造的に説明している。きめ細かい計算量理論は別の方向をとり、強指数時間仮説のような予想を用いて、具体的な多項式時間問題（編集距離、最長共通部分列）に対する正確な条件付き下界を導出し、すでにPに属することが知られている問題に対してさえ計算量理論を精緻化している。メタ計算量は、最小回路サイズ問題のような、計算量それ自体に関する問題を研究しており、その計算量の状況自体が、暗号理論および自然証明の障壁と密接に結びついた大きな未解決問題である。量子計算も古典的な問いを解決してはいない：グローバーのアルゴリズムは非構造化探索に対して2乗（指数関数的ではない）の高速化しか与えず、NP完全問題は量子コンピュータによってさえ効率的に解けることは現時点で知られていない（ $NP$ と量子クラス $BQP$ の関係自体が未解決である）。一方実務では、現代のSATおよび整数計画ソルバーは、巧妙なヒューリスティックによって数百万変数の産業用インスタンスを日常的に扱っており、最悪ケースの理論的困難性と典型的ケースの実務的困難性との間に、根強くいまだによく理解されていないギャップがあることを浮き彫りにしている。

$n=20$ のとき、 $n^3$ と $2^n$ のどちらが大きいか。

「NP」は実際には何の略か。

クック・レビンの定理によれば、史上初めてNP完全であることが証明された問題はどれか。

もし誰かがSATのような単一のNP完全問題に対する多項式時間アルゴリズムを発見したら、何が導かれるか。

参考文献

Stephen A. Cook (1971). The Complexity of Theorem-Proving Procedures · DOI:10.1145/800157.805047
Michael Sipser (2012). Introduction to the Theory of Computation
Michael R. Garey, David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness
Clay Mathematics Institute (2000). P vs NP Problem