計算可能性と P vs NP
「原理的に解けない問題」「解けても速くない問題」の違い。
- 停止性問題が決定不能であることを説明できる
- P 問題と NP 問題の違い、NP 完全の意義を述べられる
解けないことが証明されている
チューリングの停止性問題: 「任意のプログラム P と入力 x に対し、P は止まるか？」を判定する汎用プログラムは存在しないことが証明されています。万能判定器をつくることは原理的に不可能。
- 決定可能: すべての入力で停止し、正しい Yes / No を返すアルゴリズムが存在する
- 決定不能: すべての入力で停止して正答する汎用アルゴリズムは存在しない（停止性問題、整数解の存在を問うヒルベルトの第10問題など）。個々の事例まで判定できないという意味ではない
- 計算可能性は「原理的に計算できるか」の理論、計算量は「時間やメモリをどれだけ使うか」の理論
P と NP
| クラス | 定義 | 例 |
|---|---|---|
| P | 多項式時間で**判定できる決定問題** | 非負辺重みのグラフで、指定頂点間に長さ K 以下の経路があるか |
| NP | Yes の場合に、多項式長の証拠を多項式時間で検証できる決定問題 | 充足可能性（SAT）、総距離 K 以下の巡回路があるか |
| NP完全 | NP に属し、すべての NP 問題から多項式時間で帰着できる問題 | 3-SAT、グラフの3彩色可能性 |
P は NP に含まれます。速く判定できるなら、証拠に頼らず検証もできるからです。NP は「多項式時間ではない」の略ではありません。NP 完全問題へ帰着するとは、元の問題の Yes / No を保ったまま、多項式時間でその問題の入力に変換することです。ソートや最短巡回路を求める最適化問題そのものは、Yes / No の決定問題とは区別します。
盤面サイズも入力として増やせる一般化数独で、「与えられた盤面を完成できるか」を考える。完成盤面を証拠に使うと、何を検証すればよいか。
解答・解説
各行・各列・各ブロックに重複がないことと、元の数字が保たれていることを調べる。盤面のマス数の多項式回の処理で検証できるので、決定問題は NP に属する。一般化数独は NP 完全だが、固定の 9×9 盤面だけでは入力サイズが増えず、漸近計算量の議論にはならない。
「このグラフは色 3 つで塗り分けられるか」は NP 完全である。これが多項式時間で解けた場合、何が起きるか。
ヒント
NP完全の連鎖。
解答・解説
すべての NP の決定問題が多項式時間で解けるようになり **P = NP** が成立する。一方向関数の存在は P ≠ NP より強い仮定で、両者は同義ではない。P = NP は計算困難性に基づく暗号の理論的基盤に大きく影響するが、P ≠ NP が証明されても個々の暗号の安全性までは保証されない。
ハノイの塔（n 枚）の最小手数は 。全移動を1手ずつ実行する場合の計算量と、手数だけを求める場合の違いを述べよ。
解答・解説
全移動の実行には 手必要で、n に対して指数的。一方、手数を2進数で出力するだけなら n 個の 1 を並べればよく、指数回の移動を模擬する必要はない。問題が要求する出力を区別することが重要。
「無限ループだけのプログラムは止まらないと判断できるので、停止性問題は決定可能だ」という主張の誤りを説明せよ。
解答・解説
特定のプログラムについて判定できることと、任意のプログラム・入力の組すべてに正答して停止する汎用判定器があることは別である。停止性問題が否定するのは後者。