90 分で学ぶ P 対 NP 問題

第1章　導入 (6～54 ページ)
第2章　P 対 NP 問題の定義 (55～90 ページ)
第3章　P=NP の場合にわかること (91～111 ページ)
第4章　P≠NP の場合にわかること (112～226 ページ)
第5章　まとめ (227～234 ページ)

Transcript

1. P 対 NP 問題 90 分で学ぶ 2025 年 4 月 5 日 米田優峻 (@e869120)
2. 自己紹介 2 米田優峻 (よねだ まさたか) • 2002 年生まれ • 2021 年東京大学入学 • 2025/4 現在、コンピュータ科学専攻の修士 1 年 主な実績 • ICPC※ 世界大会 ‘23 銅メダル (第 9 位) • ICPC※ アジア地区決勝 ‘25 優勝 • 著書『アルゴリズム×数学』など 3 冊、世界累計 8 万部 ※大学生向けの競技プログラミングの大会
3. • 今回のスライドでは、P 対 NP 問題について、そして P 対 NP 問題の結果 によって何が起こるのかについて説明します。 • 途中やや踏み込んだ内容を含むので、わからない部分は読み飛ばしてもか まいません。特に、4.3 節は難しい内容になっています。 • しかし、第 1 章は誰でもわかるように書いたつもりです。第 1 章を読めば P 対 NP 問題が一体どういうものか、そしてどういう意義があるのかが大 体わかります。ぜひ第 1 章だけでも読んでいただければと思います。 諸注意 (1/2) 3
4. • また、本スライドは全部で 234 枚あります。 • 234 枚のスライドと聞くとびっくりする人も多いと思いますが、アニメー ションが多いので、枚数相応よりは早く読めると思います。 • また、説明のわかりやすさを優先したため、厳密な説明になっていない箇 所があります。このような部分の多くには脚注を付しています。 諸注意 (2/2) 4
5. 目次 5 1 章 導入 1.1 はじめに 1.2 本スライドの構成 2 章 P 対 NP 問題の定義 2.1 計算量の話 2.2 NP 問題とは 2.3 P 対 NP 問題の定義 3 章 P = NP の場合に起こる事 4 章 P≠NP の場合に起こる事 4.1 P≠NP でわかること 4.2 証明のアイデア 4.3 二等分問題の NP 完全性の証明 4.4 諦めるしかないのか？ 5 章 おわりに 6 ……………………… 7 ………… 54 55 …………………… 56 …………………… 65 ………… 85 91 112 ………… 113 ……………… 119 149 ……… 197 227
6. 第 1 章 導入
7. 第 1 章 導入 世の中の問題を解くにあたって、“計算回数” はとても重要である
8. はじめに 8 例として、右図の掛け算の問題を考える 2 3 9 × 3 2 8 問題
9. はじめに 9 2 3 9 × 3 2 8 問題 例として、右図の掛け算の問題を考える 単純に筆算をすると、3 桁×3 桁の掛け算に およそ 14 回くらいの計算がかかる
10. はじめに 10 2 3 9 × 3 2 8 2 Step 1 7 9×8=72 例として、右図の掛け算の問題を考える 単純に筆算をすると、3 桁×3 桁の掛け算に およそ 14 回くらいの計算がかかる
11. はじめに 11 2 3 9 × 3 2 8 1 2 Step 2 7 3×8+7 =31 3 ※足し算と掛け算をまとめて 1 回とみなす 例として、右図の掛け算の問題を考える 単純に筆算をすると、3 桁×3 桁の掛け算に およそ 14 回くらいの計算がかかる※
12. はじめに 12 2 3 9 × 3 2 8 1 9 1 2 Step 3 7 2×8+3 =19 3 ※足し算と掛け算をまとめて 1 回とみなす 例として、右図の掛け算の問題を考える 単純に筆算をすると、3 桁×3 桁の掛け算に およそ 14 回くらいの計算がかかる※
13. はじめに 13 2 3 9 × 3 2 8 1 9 1 2 8 Step 4 7 9×2=18 3 1 ※足し算と掛け算をまとめて 1 回とみなす 例として、右図の掛け算の問題を考える 単純に筆算をすると、3 桁×3 桁の掛け算に およそ 14 回くらいの計算がかかる※
14. はじめに 14 2 3 9 × 3 2 8 1 9 1 2 7 8 Step 5 7 3×2+1=7 3 1 ※足し算と掛け算をまとめて 1 回とみなす 例として、右図の掛け算の問題を考える 単純に筆算をすると、3 桁×3 桁の掛け算に およそ 14 回くらいの計算がかかる※
15. はじめに 15 2 3 9 × 3 2 8 1 9 1 2 4 7 8 Step 6 7 2×2=4 3 1 ※足し算と掛け算をまとめて 1 回とみなす 例として、右図の掛け算の問題を考える 単純に筆算をすると、3 桁×3 桁の掛け算に およそ 14 回くらいの計算がかかる※
16. はじめに 16 2 3 9 × 3 2 8 1 9 1 2 4 7 8 7 Step 7 7 9×3=27 3 1 2 ※足し算と掛け算をまとめて 1 回とみなす 例として、右図の掛け算の問題を考える 単純に筆算をすると、3 桁×3 桁の掛け算に およそ 14 回くらいの計算がかかる※
17. はじめに 17 2 3 9 × 3 2 8 1 9 1 2 4 7 8 1 7 Step 8 7 3×3+2=11 3 1 2 1 ※足し算と掛け算をまとめて 1 回とみなす 例として、右図の掛け算の問題を考える 単純に筆算をすると、3 桁×3 桁の掛け算に およそ 14 回くらいの計算がかかる※
18. はじめに 18 2 3 9 × 3 2 8 1 9 1 2 4 7 8 7 1 7 Step 9 7 2×3+1=7 3 1 2 1 ※足し算と掛け算をまとめて 1 回とみなす 例として、右図の掛け算の問題を考える 単純に筆算をすると、3 桁×3 桁の掛け算に およそ 14 回くらいの計算がかかる※
19. はじめに 19 2 3 9 × 3 2 8 1 9 1 2 4 7 8 7 1 7 2 Step 10 7 3 1 2 1 ※足し算と掛け算をまとめて 1 回とみなす 例として、右図の掛け算の問題を考える 単純に筆算をすると、3 桁×3 桁の掛け算に およそ 14 回くらいの計算がかかる※
20. はじめに 20 2 3 9 × 3 2 8 1 9 1 2 4 7 8 7 1 7 9 2 Step 11 7 3 1 2 1 1+8=9 ※足し算と掛け算をまとめて 1 回とみなす 例として、右図の掛け算の問題を考える 単純に筆算をすると、3 桁×3 桁の掛け算に およそ 14 回くらいの計算がかかる※
21. はじめに 21 2 3 9 × 3 2 8 1 9 1 2 4 7 8 7 1 7 3 9 2 Step 12 7 3 1 2 1 9+7+7=23 2 ※足し算と掛け算をまとめて 1 回とみなす 例として、右図の掛け算の問題を考える 単純に筆算をすると、3 桁×3 桁の掛け算に およそ 14 回くらいの計算がかかる※
22. はじめに 22 2 3 9 × 3 2 8 1 9 1 2 4 7 8 7 1 7 8 3 9 2 Step 13 7 3 1 2 1 1+4+1+2=8 2 ※足し算と掛け算をまとめて 1 回とみなす 例として、右図の掛け算の問題を考える 単純に筆算をすると、3 桁×3 桁の掛け算に およそ 14 回くらいの計算がかかる※
23. はじめに 23 2 3 9 × 3 2 8 1 9 1 2 4 7 8 7 1 7 7 8 3 9 2 Step 14 7 3 1 2 1 2 ※足し算と掛け算をまとめて 1 回とみなす 例として、右図の掛け算の問題を考える 単純に筆算をすると、3 桁×3 桁の掛け算に およそ 14 回くらいの計算がかかる※
24. はじめに 24 2 3 9 × 3 2 8 1 9 1 2 4 7 8 7 1 7 7 8 3 9 2 Step 14 7 3 1 2 1 2 14 回の計算で 結果が 78392 であるとわかる ※足し算と掛け算をまとめて 1 回とみなす 例として、右図の掛け算の問題を考える 単純に筆算をすると、3 桁×3 桁の掛け算に およそ 14 回くらいの計算がかかる※
25. はじめに 25 2 3 9 × 3 2 8 1 9 1 2 4 7 8 7 1 7 7 8 3 9 2 例として、右図の掛け算の問題を考える 単純に筆算をすると、3 桁×3 桁の掛け算に およそ 14 回くらいの計算がかかる※ そして同じ方法を使うと、一般に n 桁× n 桁に n2 回くらいの計算がかかる Step 14 7 3 1 2 1 2 14 回の計算で 結果が 78392 であるとわかる ※足し算と掛け算をまとめて 1 回とみなす
26. はじめに 26 しかし、もし掛け算が n1.5 回の計算で出来たら？
27. はじめに 27 しかし、もし掛け算が n1.5 回の計算で出来たら？ 100 万桁の掛け算の場合… 筆算 新たな方法 ……… 1,000,000,000,000 回 …… 1,000,000,000 回 (1 兆回) (10 億回) 千倍差
28. はじめに 28 しかし、もし掛け算が n1.5 回の計算で出来たら？ 100 万桁の掛け算の場合… 筆算 新たな方法 ……… 1,000,000,000,000 回 …… 1,000,000,000 回 (1 兆回) (10 億回) 千倍差 このように、計算回数の改善は 大きな違いを生む！
29. はじめに 29 そして計算回数は掛け算だけでなく 世の中の様々な問題を解くにあたって重要になる 最短経路の探索 グーグル検索 生成 AI の学習 AI
30. はじめに 30 ここで、計算回数の中でも特に 多項式回 (n2 回, n3 回など) で解けるか それとも指数 (2n など) になってしまうかは重要
31. なぜ多項式が重要？ 31 n = 10000 でも 計算可能 多項式回の場合、たとえ計算回数が n3 回※ であっても n が 1 万程度であればパソコンでも現実的な時間で計算できる (PC の演算速度は処理によるが、毎秒数億～数十億回程度) n3 ※ n200 回などであれば別だが、アルゴリズムの世界では、このような計算回数は非常に稀
32. なぜ多項式が重要？ 32 n = 100 ですら 絶対不可能 しかし指数になってしまった場合、n = 100 でも絶望的 たとえば 2 の 100 乗はおよそ 1 京の 100 兆倍 最先端のスパコン (毎秒数百京回) でも何万年もかかってしまう… 2n
33. なぜ多項式が重要！ 33 n3 2n したがって、計算回数を「指数回」にするのは 出来る限り避けたいことである
34. 第 1 章 導入 しかし、世の中には “どうしても指数になってしまう” と予想されている難問が存在する
35. 難問の例: 部分和問題 35 目の前に n = 5 枚のカードが置かれている 合計が 1 億になるように、いくつかのカードを選べるか？ 21351486 23376139 32531866 55272375 67478134
36. 難問の例: 部分和問題 36 合計 21351486 もちろん、あり得る選び方を全部調べてみると 最終的には答えがわかる 1 通り目 21351486 23376139 32531866 55272375 67478134
37. 難問の例: 部分和問題 37 合計 23376139 もちろん、あり得る選び方を全部調べてみると 最終的には答えがわかる 2 通り目 21351486 23376139 32531866 55272375 67478134
38. 難問の例: 部分和問題 38 合計 57297028 もちろん、あり得る選び方を全部調べてみると 最終的には答えがわかる 3 通り目 21351486 23376139 32531866 55272375 67478134
39. 難問の例: 部分和問題 39 合計 32531866 もちろん、あり得る選び方を全部調べてみると 最終的には答えがわかる 4 通り目 21351486 23376139 32531866 55272375 67478134
40. 難問の例: 部分和問題 40 合計 53883352 もちろん、あり得る選び方を全部調べてみると 最終的には答えがわかる 5 通り目 21351486 23376139 32531866 55272375 67478134
41. 難問の例: 部分和問題 41 合計 55988005 もちろん、あり得る選び方を全部調べてみると 最終的には答えがわかる 6 通り目 21351486 23376139 32531866 55272375 67478134
42. 難問の例: 部分和問題 42 合計 77259491 もちろん、あり得る選び方を全部調べてみると 最終的には答えがわかる 7 通り目 21351486 23376139 32531866 55272375 67478134
43. 難問の例: 部分和問題 43 合計 55272375 もちろん、あり得る選び方を全部調べてみると 最終的には答えがわかる 8 通り目 21351486 23376139 32531866 55272375 67478134
44. 難問の例: 部分和問題 44 合計 76623861 もちろん、あり得る選び方を全部調べてみると 最終的には答えがわかる 9 通り目 21351486 23376139 32531866 55272375 67478134
45. 難問の例: 部分和問題 45 合計 78648514 もちろん、あり得る選び方を全部調べてみると 最終的には答えがわかる 10 通り目 21351486 23376139 32531866 55272375 67478134
46. 難問の例: 部分和問題 46 合計 100000000 もちろん、あり得る選び方を全部調べてみると 最終的には答えがわかる 11 通り目 21351486 23376139 32531866 55272375 67478134
47. 難問の例: 部分和問題 47 合計 100000000 もちろん、あり得る選び方を全部調べてみると 最終的には答えがわかる 11 通り目 21351486 23376139 32531866 55272375 67478134 見つかった！ 答えは Yes
48. • しかし、この方法ではカードの枚数を n とするとき、最大 2 の n 乗通りのパターンを調べる必要があり、残念ながら指数 になってしまう • また、工夫して 2 の n/2 乗回程度の計算で解く方法も知られて いるが、これでも指数からは逃れられていない 難問の例: 部分和問題 48
49. 第 1 章 導入 それでは、部分和問題のような問題は 結局指数から逃れられないのか？ それとも、もっと効率的に解く方法があるのか？
50. 第 1 章 導入 それでは、部分和問題のような問題は 結局指数から逃れられないのか？ それとも、もっと効率的に解く方法があるのか？ これが P 対 NP 問題！
51. P 対 NP 問題の答えはまだ分かっていない。しかし… • P 対 NP 問題の答えが No (指数から逃れられない) になった場合、部分 和問題を含む数百の問題が同時に、効率的に解けないことがわかる • P 対 NP 問題の答えが Yes (効率的に解ける) になった場合、これまで作 られた暗号の安全性が根本から揺らぐことになる • どちらにせよ、世の中に及ぼす影響は非常に大きい P 対 NP 問題の結末 51
52. 第 1 章 導入 52 そのため、P 対 NP 問題には 1 億円超の懸賞金がかけられている
53. 第 1 章 導入 53 そしてそれ以上に、P 対 NP 問題に関する知識は 情報科学の分野でとても重要
54. 本スライドの構成 54 そこで、本スライドでは P 対 NP 問題について、以下の内容を中心に 詳しく解説します 第 2 章 P 対 NP 問題の定義 第 3 章 答えが Yes の時の影響 (暗号などの重要な概念の紹介を含む) 第 4 章 答えが No の時の影響 (多項式時間帰着などの概念を含む)
55. 第 2 章 P 対 NP 問題の定義
56. 2.1 2.2 前提: 計算量とは 前提: NP 問題とは 2.3 P 対 NP 問題の定義
57. • 問題を解くのに必要な計算回数 (例: 掛け算の筆算の場合 n2 回) のこ とを、情報科学の世界では計算量という • ここで、計算量は n2 + 5 回や 2n3 + 15n 回のように、正確に表すこ ともできなくはない 計算量とは 57
58. • しかし、計算量の正確な見積もりは困難な場合が多い※ • さらに、計算量を正確に見積もろうとすると、数え方によって計算 量が変わってしまうことがある • 例1: 筆算の足し算と掛け算をまとめた場合、n2 + 2n – 1 回 • 例2: 筆算の足し算と掛け算を別にした場合、2n2 + n – 1 回 • 例3: 最終段階の足し算までを別にした場合、3n2 – 1 回 計算量とは 58 ※実際、筆算が大体 n2 回くらいであることはすぐわかるが、n2 + 2n – 1 回であることを考えるには時間がかかる
59. 計算量の表し方 59 そこで情報科学の世界では、一般的に計算回数として 「大まかな計算量」を考えることが多い たとえば n2 + 15 回も 2n2 回も 0.5n2 回も「n2 回程度」とみなされる n2 + 15 回 2n2 回 0.5n2 + n 回 n2 回 程度
60. 計算量の表し方 60 そして一般的には、大体 n2 回であることを「計算量が n2 回」であると は言わず、「計算量は O(n2) である」のように O を付けて表す。 このような表記法を O 記法 (オーダー記法) という。 参考: O 記法の定義 計算量の定数部分 (2n3 の 2) と小さい項 (3n4 + n の n) を除いた表記。 • 例: 計算回数が 2n3 回の場合 → 計算量は O(n3) • 例: 計算回数が 3n4 + n 回の場合 → 計算量は O(n4) ※もっと厳密な O 記法の定義はあるが、ここでは “簡単な” 定義を示す
61. 計算量の表し方 61 ここで、計算量が多項式以下であることを多項式時間、そうではなく指 数になってしまうことを指数時間という ※補足: log n は多項式でないが、明らかに多項式以下なので多項式時間 多項式時間 指数時間 O(n2) O(n3) O(log n) O(2n) O(3n) ※計算量 O(2n×n) など「指数ですらない」ものも存在するが、ここでは略
62. 重要な注意 (1/2) 62 注意: 一般的に多項式時間とは、入力の長さに対する多項式時間である ことを指す よくある間違い n の 2 以上の最小の約数を求める問題を考える。右図の ように 2, 3, …, n で割れば計算量 O(n) で解ける。O(n) は多項式であるため、一見多項式時間に見える。 しかし入力長に対する多項式ではないため、実際の計 算量は「指数時間」である (詳細は次ページ)。 n は 2 で割れるか？ n は 3 で割れるか？ n は n で割れるか？
63. 重要な注意 (2/2) 63 具体的には、入力の文字数を m とするとき、前述の方法では「〇 が △ で 割れるか」を 10m 回くらい調べる必要がある※ したがって、多項式時間ではなく指数時間！ 例 1 9 9 7 n = 文字数 m = 3 例 2 9 9 9 9 1 n = 文字数 m = 5 → n = 103 回くらい調べる必要がある！ → n = 105 回くらい調べる必要がある！ ※厳密には、計算量理論の世界では入力が 2 進法で表されるので実際には 2m 回となるが、ここでは深く考えないことにする
64. • 多項式時間で解ける問題のことを「この問題は P である」ということ がある※ • たとえば掛け算は多項式時間 (n 桁×n 桁の筆算で O(n2)) で解けるの で、掛け算は P である 補足 64 ※多項式は英語で Polynomial と書き、それを略すと P となる
65. 2.1 2.2 前提: 計算量とは 前提: NP 問題とは 2.3 P 対 NP 問題の定義
66. 準備 66 まず、判定問題とは答えが存在するかどうかを判定する問題のこ とを指す。特に Yes の場合はあり得る答えのうち 1 つを出力しな ければならない。※ ※判定問題のことを決定問題ということもある
67. 準備 67 判定問題の例 整数 N を 2 以上の整数の掛け算で表す方法は存在するか？ • N = 2025 の場合、答えは Yes で、25×81 という解を出力 • N = 2017 の場合、答えは No まず、判定問題とは答えが存在するかどうかを判定する問題のこ とを指す。特に Yes の場合はあり得る答えのうち 1 つを出力しな ければならない。
68. 準備 68 判定問題でない例 東京から大阪までは最短何時間で行けるか？ Yes/No を判定する問題ではないので判定問題ではない しかし「4 時間以内で行く方法はあるか？」にすると判定問題に まず、判定問題とは答えが存在するかどうかを判定する問題のこ とを指す。特に Yes の場合はあり得る答えのうち 1 つを出力しな ければならない。
69. 準備 69 次に、NP 問題とは判定問題のうち、答えが Yes のときに多項式 時間で「合っているかの検証」ができる問題のことを指す (難しい概念なので、以降具体例を 5 個説明します)
70. 例 1: 素因数分解問題 70 問題 整数 N を 2 以上の整数の掛け算で表す方法はあるか？ 例 N = 2025 → Yes (25×81) N = 2017 → No
71. 例 1: 素因数分解問題 71 問題 整数 N を 2 以上の整数の掛け算で表す方法はあるか？ 例 N = 2025 → Yes (25×81) N = 2017 → No これは判定問題である また、答えが Yes の場合の検証 (25×81 は本当に 2025 か？) は単に掛け 算をするだけで良いので多項式時間で出来る → よって NP 問題
72. 例 2: 部分和問題 72 問題 N 個の数が書かれている。その中からいくつかを選び、合計を ぴったり S にする方法はあるか？ 例 N = 5, S = 100, 書かれている数が 16, 25, 28, 43, 47 → Yes (25, 28, 47 を選べば合計 100) 16 25 28 43 47
73. 例 2: 部分和問題 73 例 N = 5, S = 100, 書かれている数が 16, 25, 28, 43, 47 → Yes (25, 28, 47 を選べば合計 100) これは判定問題である また、答えが Yes の場合の検証 (本当に合計が 100 か？) は単に足し算を すれば良いので多項式時間で出来る → よって NP 問題 問題 N 個の数が書かれている。その中からいくつかを選び、合計を ぴったり S にする方法はあるか？
74. 例 3: 二等分問題※ 74 問題 N 個の数が書かれている。合計が同じになるように 2 つのグルー プに分割することはできるか？ 例 N = 5, 書かれている数が 20, 35, 40, 55, 70 → Yes (下図のように分割) 40 70 20 35 55 合計 110 合計 110 ※分割問題と呼ばれることも多いが、ここではわかりやすさのため二等分問題と記す
75. 例 3: 二等分問題※ 75 例 これは判定問題である また、答えが Yes の場合の検証 (本当に合計が同じか？) は前の例と同様に 足し算をすればよいので、多項式時間で出来る → よって NP 問題 N = 5, 書かれている数が 20, 35, 40, 55, 70 → Yes (下図のように分割) ※分割問題と呼ばれることも多いが、ここではわかりやすさのため二等分問題と記す 問題 N 個の数が書かれている。合計が同じになるように 2 つのグルー プに分割することはできるか？
76. 例 4: ハミルトン閉路問題 76 問題 道路ネットワークが与えられる。都市をちょうど一度ずつ巡って スタート地点に移動する方法はあるか？ 例 道路網が左図のような場合 → Yes (右図のような経路) S S スタート 地点
77. 例 4: ハミルトン閉路問題 77 例 道路網が左図のような場合 → Yes (右図のような経路) これは判定問題である また、答えが Yes の場合の検証 (本当に都市を一度ずつ巡っているか？) も 都市数を N とするとき計算量 O(N)、つまり多項式時間で出来る よって NP 問題 問題 道路ネットワークが与えられる。都市をちょうど一度ずつ巡って スタート地点に移動する方法はあるか？
78. 例 5: 巡回セールスマン問題 78 問題 道路ネットワークが与えられる。都市をちょうど一度ずつ巡って スタート地点に戻るには、最短何時間かかるか？ 例 道路網が右図のような場合 → 10 時間 (A, B, C, A の順に行けばよい) A B C 3 1 6 4 5 2
79. 例 5: 巡回セールスマン問題 79 例 道路網が右図のような場合 → 10 時間 (A, B, C, A の順に行けばよい) この問題は判定問題ではないので、NP ではない！ (補足: 今回のように最短・最小を求める問題のことを最適化問題という) 問題 道路ネットワークが与えられる。都市をちょうど一度ずつ巡って スタート地点に戻るには、最短何時間かかるか？
80. 例 5: 巡回セールスマン問題 80 例 道路網が右図のような場合 → 10 時間 (A, B, C, A の順に行けばよい) この問題は判定問題ではないので、NP ではない！ (補足: 今回のように最短・最小を求める問題のことを最適化問題という) 問題 道路ネットワークが与えられる。都市をちょうど一度ずつ巡って スタート地点に戻るには、最短何時間かかるか？ そこで問題を少し変えてみると…
81. 例 5: 巡回セールスマン問題 (判定版) 81 問題 道路ネットワークが与えられる。都市をちょうど一度ずつ巡って スタート地点に戻ることを考える。10 時間以内で達成する方法は あるか？
82. 例 5: 巡回セールスマン問題 (判定版) 82 これは判定問題である また、答えが Yes の場合の検証 (本当に 10 時間以内か？) も都市数を N と するとき計算量 O(N)、つまり多項式時間で出来る よって NP 問題 問題 道路ネットワークが与えられる。都市をちょうど一度ずつ巡って スタート地点に戻ることを考える。10 時間以内で達成する方法は あるか？
83. NP 問題まとめ 83 このように、世の中の沢山の問題が NP 問題である！ ※もちろん、(今回は例を挙げなかったが) 判定問題であっても多項式時間で検証できない場合は NP にならないことに注意 二等分問題 ハミルトン 閉路問題 巡回セールス (判定版) 20 30 40 50 素因数分解 部分和問題 20 30 40 50 100 50 20 40 30
84. よくある誤解 84 NP 問題は多項式時間で解けない問題 (not 多項式 = not P) とよく誤解されるが、これは間違い 多項式時間で 解けない問題 多項式時間で 検証ができる 判定問題
85. 2.1 前提: 計算量とは 2.3 P 対 NP 問題の定義 2.2 前提: NP 問題とは
86. P 対 NP 問題の定義 86 P 対 NP 問題は すべての NP 問題が多項式時間で解けるか？という問題 部分和問題 ハミルトン 閉路問題 巡回セールス (判定版) 全部 多項式時間 で解ける？ 20 30 40 50 100
87. P 対 NP 問題の定義 87 すべての NP 問題が 多項式時間で解けることを それに対して そうではないことを P = NPという P ≠ NPという
88. P 対 NP 問題の定義 88 それでは、一体どちらが正解？
89. P 対 NP 問題の正解 • 多くの研究者は、P≠NP (つまり多項式時間では解けない NP 問題 がある) と予想している • しかし、P = NP を予想する者もおり、名著 The Art of Computer Programming を書いた大物研究者 Donald Knuth は P = NP を予想 89 Donald Knuth P≠NPを証明する 試みはことごとく 失敗している ※吹き出し内のセリフは Wikipedia の「P≠NP予想」より引用
90. • なお、賭けサイト Metaculus では「P = NP の確率は 3%」と予想されて いる (※専門家の意見ではない) 補足 90 ※https://www.metaculus.com/questions/1408/p-np-is-true/
91. 第 3 章 P = NP の場合に起こること
92. P = NP の場合に起こること • P = NP の場合、巡回セールスマン問題 (判定版) を含むすべて の NP 問題を多項式時間で解けることになる • しかし、これは暗号を多項式時間で破れることにも繋がるため、 今使われている暗号の安全性が根本から崩壊する 92
93. P = NP の場合に起こること • P = NP の場合、巡回セールスマン問題 (判定版) を含むすべて の NP 問題を多項式時間で解けることになる • しかし、これは暗号を多項式時間で破れることにも繋がるため、 今使われている暗号の安全性が根本から崩壊する 93 暗号が崩壊するとはどういうことか？ まずは暗号の仕組みから説明します
94. 暗号の仕組み 94 教員の米田です。残念なが ら、あなたの期末試験の… 前提として、暗号を使わずに “そのまま” 通信した場合 盗聴できたとき※ に、他人に知られたくない文章がばれてしまう 教員の米田です。残念なが ら、あなたの期末試験の… 通信 ※データが不正に流出することをイメージすればよい 送信者 (教員) の PC 受信者 (生徒) の PC 盗聴者 アイツまた 赤点取ったのか バカだな！
95. 暗号の仕組み 95 教員の米田です。残念なが ら、あなたの期末試験の… そこで暗号では、最初に暗号化して読めなくした後 最後に受信者が復号するという方式を取る 647983148948789859267 900142156058984223928 ① 暗号化 受信者 (生徒) の PC
96. 暗号の仕組み 96 教員の米田です。残念なが ら、あなたの期末試験の… そこで暗号では、最初に暗号化して読めなくした後 最後に受信者が復号するという方式を取る 647983148948789859267 900142156058984223928 647983148948789859267 900142156058984223928 ① 暗号化 ② 通信
97. 暗号の仕組み 97 教員の米田です。残念なが ら、あなたの期末試験の… そこで暗号では、最初に暗号化して読めなくした後 最後に受信者が復号するという方式を取る 教員の米田です。残念なが ら、あなたの期末試験の… 647983148948789859267 900142156058984223928 647983148948789859267 900142156058984223928 ① 暗号化 ③ 復号 ② 通信
98. 暗号の仕組み 98 教員の米田です。残念なが ら、あなたの期末試験の… そこで暗号では、最初に暗号化して読めなくした後 最後に受信者が復号するという方式を取る 647983148948789859267 900142156058984223928 ① 暗号化 ② 通信 盗聴者 数字の羅列 だけでは何も わからねえ… 教員の米田です。残念なが ら、あなたの期末試験の… 647983148948789859267 900142156058984223928 ③ 復号
99. 暗号の仕組み 99 暗号には様々なものがあるが 最も代表的な暗号の 1 つとして RSA 暗号 ※もしかしたら最近は楕円曲線暗号の方が使われているかもしれないが、説明のしやすさのため RSA 暗号を取り上げる がある
100. RSA 暗号の仕組み (1/6) 100 RSA 暗号ではまず、公開鍵 𝑛, 𝑒 および秘密鍵 𝑑 が準備される 公開鍵 𝑛 は 2 つの素数の積になる必要がある (ここでは 11×31 = 341) 公開鍵 n = 341 e = 139 秘密鍵 d = ???
101. RSA 暗号の仕組み (2/6) 101 RSA 暗号ではまず、公開鍵 𝑛, 𝑒 および秘密鍵 𝑑 が準備される 公開鍵 𝑛 は 2 つの素数の積になる必要がある (ここでは 11×31 = 341) 公開鍵 n = 341 e = 139 秘密鍵 d = 259 139×259 を 10×30=300 で 割った余りは 1 だから d = 259 だ！
102. RSA 暗号の仕組み (3/6) 102 文章 (デジタルデータなので数値で表される) を送信するときは 最初に受信者のパソコンの公開鍵を入手する 文章 公開鍵 n = 341 e = 139 200 公開鍵 n = 341 e = 139 秘密鍵 d = 259 ① 鍵の入手
103. RSA 暗号の仕組み (4/6) 103 次に、暗号化を行う 暗号は「元の文章の 𝑒 乗を 𝑛 で割った余り」とする 文章 公開鍵 n = 341 e = 139 200 暗号 193 ② 暗 号 化 200139 を 341 で 割った余りは 193 公開鍵 n = 341 e = 139 秘密鍵 d = 259 ① 鍵の入手
104. RSA 暗号の仕組み (5/6) 104 次に、暗号化を行う 暗号は「元の文章の 𝑒 乗を 𝑛 で割った余り」とする 暗号 193 ② 暗 号 化 公開鍵 n = 341 e = 139 秘密鍵 d = 259 ① 鍵の入手 ③ 送信 暗号 193 文章 公開鍵 n = 341 e = 139 200
105. RSA 暗号の仕組み (6/6) 105 次に、暗号化を行う 暗号は「元の文章の 𝑒 乗を 𝑛 で割った余り」とする 暗号 193 ② 暗 号 化 ① 鍵の入手 ③ 送信 暗号 193 文章 200 ④ 復 号 193259 を 341 で割った余りは 200 文章 公開鍵 n = 341 e = 139 200 公開鍵 n = 341 e = 139 秘密鍵 d = 259
106. RSA 暗号の仕組み (6/6) 106 次に、暗号化を行う 暗号は「元の文章の 𝑒 乗を 𝑛 で割った余り」とする 文章 公開鍵 n = 341 e = 139 200 暗号 193 ② 暗 号 化 公開鍵 n = 341 e = 139 秘密鍵 d = 259 ① 鍵の入手 ③ 送信 暗号 193 文章 200 ④ 復 号 193259 を 341 で割った余りは 200 すると、必ず元の文章が復元できる これが RSA 暗号！ (復元できる理由は、フェルマーの小定理を使えば証明できるが今回は省略)
107. • 今回の例では 𝑛 として 341 という数を用いたが、実際には 1000 桁くらいの数が利用される • もし 𝑛 が 1000 桁程度の数になっても、繰り返し二乗法や拡張 ユークリッドの互除法などの高度なテクニックを使うと、暗号 化の際の累乗の計算や秘密鍵 𝑑 の計算を十分高速に行うこと ができる RSA 暗号の重要な補足 107
108. RSA 暗号の重要な補足 108 ここで、もし 𝑛 の素因数分解ができれば 公開鍵 𝑒 から秘密鍵 𝑑 を計算することができ、盗聴に成功する 341 11 31
109. RSA 暗号の重要な補足 109 しかし、現在 1000 桁程度の素因数分解を高速に行う手法は 発見されておらず、これが暗号の安全性を保証している 341 11 31 不可能！
110. • しかし、もし P = NP の場合、すべての NP 問題が多項式時間 で解けることになる • 素因数分解問題は NP 問題であるため (→ p.69)、素因数分解問 題も多項式時間で解けることになる P = NP の世界 110 暗号が破られる可能性が大きく高まるため、暗号の安全性が 根本から崩れてしまう！
111. • もちろん、RSA 暗号の他にも ElGamal 暗号や楕円曲線暗号な どの様々な暗号が存在する • しかし、P = NP が成立した場合、全部が多項式時間で破られ ることになり、大問題 P = NP の世界 111
112. 第 4 章 P ≠ NP の場合に起こること
113. P ≠ NP の場合に起こること • それでは、逆に P ≠ NP の場合は何が起こるのか？ • 実は、部分和問題を含む数百の問題について、同時に多項式時 間で解けないということがわかる 113
114. P ≠ NP の場合に起こること 114 具体的には、上記のような有名問題が 全部 “多項式時間で解けない” ということがわかる ハミルトン閉路問題 巡回セールスマン問題 最大独立集合問題 最小頂点被覆問題 ナップザック問題 SAT 問題 グラフ彩色問題 ビンパッキング問題 テトリス 数独 部分和問題 二等分問題
115. P ≠ NP の場合に起こること 115 なぜ？
116. • 実は、NP 問題の中で最も難しいと証明 されている問題 (これが多項式時間で解 けたら他全部多項式時間で解ける) がい くつか存在する • このような問題を NP 完全といい、前述 の部分和問題なども NP 完全に該当する P ≠ NP の場合に起こること 116 すべての NP 問題 NP 完全 ※巡回セールスマン問題などは、2 章で述べたように判定版にすると NP 完全になる (そうでない場合はそもそも NP 問題ではない)
117. P ≠ NP の場合に起こること 117 もちろん、NP 問題がどこまで多項式で解けるか (上図) は未知だが NP 完全は “NP 問題の中で最強” なので P ≠ NP ならば絶対に多項式時間で解けないことになる NP 完全 多 項 式 NP 完全 多 項 式 NP 完全 多 項 式 ※この場合 P = NP
118. • それでは、部分和問題などが NP 完全であることはどうやって 証明するのか？ • 4.2 節では証明のアイデアを紹介し、4.3 節では具体例として 二等分問題 (→ p.73) が NP 完全であることを証明する 本章の構成 118
119. 4.1 4.2 4.3 4.4 P≠NP でわかること 証明のアイデア 二等分問題が NP 完全である証明 諦めるしかないのか？
120. 証明のアイデア 120 ステップ 1 以下の “Cook-Levin の定理” が成り立つ (証明は難しい) SAT 問題 (→ p.133) は NP 完全である。すなわち、SAT 問題は他のどの NP 問題と比べても、同程度以上に難しい。 SAT 問題 他の NP 問題 他の NP 問題 他の NP 問題 難しい
121. 証明のアイデア 121 ステップ 2 SAT 問題が NP 完全であることが分かったので、他の問題が SAT と同程度以上に難しい※ ことを段階的に証明する たとえば二等分問題 (→ p.73) の場合、以下の手順で証明する ※この問題が多項式時間で解けたら、SAT も多項式時間で解けるという意味 1 3SAT 問題が SAT 問題と同程度以上に難しいことを証明 2 部分和問題が 3SAT 問題と同程度以上に難しいことを証明 3 二等分問題が部分和問題と同程度以上に難しいことを証明
122. 証明のアイデア 122 それでは、問題 B が問題 A と同程度以上に難しいことは どう証明すればいいのか？ 問題 A が問題 B の特殊ケースに なっていることを言えばよい！
123. • 問題 A を「問題 B の特殊ケース」に多項式時間で変換するこ とを多項式時間帰着という • 多項式時間帰着できた場合、もし問題 B が多項式時間で解け るならば問題 A も多項式時間で解けることがわかる (なぜなら、 A を B に変換した後に B を解けばよいため) 多項式時間帰着 123 問題 A 問題 B 解答 変換 (多項式時間) 解く (多項式時間)
124. • 問題 A を「問題 B の特殊ケース」に多項式時間で変換するこ とを多項式時間帰着という • 多項式時間帰着できた場合、もし問題 B が多項式時間で解け るならば問題 A も多項式時間で解けることがわかる (なぜなら、 A を B に変換した後に B を解けばよいため) 多項式時間帰着 124 問題 A 問題 B 解答 変換 (多項式時間) 解く (多項式時間) たとえば、変換に O(n2) かかって 解くのに O(n3) かかった場合 全体で O(n3) となるが、これは多項式時間
125. 多項式時間帰着 125 難しい概念なので 多項式時間帰着の例を 2 つ挙げます
126. 例 1: 二乗と掛け算 126 整数 N が入力される。 N の 2 乗を計算せよ。 整数 A, B が入力される。 A×B を計算せよ。 二乗問題 掛け算問題 帰着
127. 例 1: 二乗と掛け算 127 整数 A, B が入力される。 A×B を計算せよ。 帰着 N×N の掛け算を考えれば、二乗問題は掛け算問題の特殊ケースになってお り、変換も多項式時間で出来る※ したがって、二乗問題は掛け算問題に多項式時間帰着可能 ※ A, B の値として N, N を入力すればいいだけなので、明らかに多項式時間 掛け算問題 整数 N が入力される。 N の 2 乗を計算せよ。 二乗問題
128. 例 1: 二乗と掛け算 128 整数 A, B が入力される。 A×B を計算せよ。 帰着 N×N の掛け算を考えれば、二乗問題は掛け算問題の特殊ケースになってお り、変換も多項式時間で出来る※ したがって、二乗問題は掛け算問題に多項式時間帰着可能 ※ A, B の値として N, N を入力すればいいだけなので、明らかに多項式時間 掛け算問題 整数 N が入力される。 N の 2 乗を計算せよ。 二乗問題 つまり、掛け算問題は 二乗問題と同程度以上に難しい！
129. 例 2: 二等分問題と部分和問題 129 二等分問題 合計が等しくなるように、N 個の 整数を 2 分割することは可能？ 部分和問題 帰着 合計が S になるように、N 個の整 数から何個かを選ぶことは可能？ 20 35 45 60 20 60 35 45 20 30 40 50 20 30 50 合計 100
130. 例 2: 二等分問題と部分和問題 130 合計が等しくなるように、N 個の 整数を 2 分割することは可能？ 帰着 合計が S になるように、N 個の整 数から何個かを選ぶことは可能？ S を「N 個の数の合計÷2」にすることを考えれば、二等分問題は部分和問題 の特殊ケースになっており、変換も多項式時間で出来る したがって、二等分問題は部分和問題に多項式時間帰着可能 二等分問題 部分和問題
131. 例 2: 二等分問題と部分和問題 131 合計が等しくなるように、N 個の 整数を 2 分割することは可能？ 帰着 合計が S になるように、N 個の整 数から何個かを選ぶことは可能？ S を「N 個の数の合計÷2」にすることを考えれば、二等分問題は部分和問題 の特殊ケースになっており、変換も多項式時間で出来る したがって、二等分問題は部分和問題に多項式時間帰着可能 二等分問題 部分和問題 つまり、部分和問題は 二等分問題と同程度以上に難しい！
132. まとめると、以下のステップで問題 X が NP 完全であることが証 明できる ここまでのまとめ 132 1 2 Cook-Levin の定理を使って、SAT 問題が NP 完全である ことを証明する 多項式時間帰着を使って、問題 X が SAT 問題と同程度以 上に難しいことを証明する
133. ところで 133 Cook-Levin で出てきた SAT 問題は どういう問題？
134. SAT 問題 (充足可能性問題) とは 134 以下の条件をすべて満たす x 1 , x 2 , x 3 , x 4 (0 か 1 を取る) は存在するか？ • x 1 = 0 または x 2 = 1 または x 3 = 1 である • x 1 = 1 または x 2 = 1 または x 4 = 0 である • x 2 = 0 または x 4 = 1 である • x 3 = 1 または x 4 = 1 である まずは具体例から考えてみよう
135. SAT 問題 (充足可能性問題) とは 135 以下の条件をすべて満たす x 1 , x 2 , x 3 , x 4 (0 か 1 を取る) は存在するか？ • x 1 = 0 または x 2 = 1 または x 3 = 1 である • x 1 = 1 または x 2 = 1 または x 4 = 0 である • x 2 = 0 または x 4 = 1 である • x 3 = 1 または x 4 = 1 である まずは具体例から考えてみよう (x 1 , x 2 , x 3 , x 4 ) = (0, 0, 0, 0) → 4 つめの条件を満たさない
136. SAT 問題 (充足可能性問題) とは 136 以下の条件をすべて満たす x 1 , x 2 , x 3 , x 4 (0 か 1 を取る) は存在するか？ • x 1 = 0 または x 2 = 1 または x 3 = 1 である • x 1 = 1 または x 2 = 1 または x 4 = 0 である • x 2 = 0 または x 4 = 1 である • x 3 = 1 または x 4 = 1 である まずは具体例から考えてみよう (x 1 , x 2 , x 3 , x 4 ) = (0, 0, 0, 1) → 2 つめの条件を満たさない
137. SAT 問題 (充足可能性問題) とは 137 以下の条件をすべて満たす x 1 , x 2 , x 3 , x 4 (0 か 1 を取る) は存在するか？ • x 1 = 0 または x 2 = 1 または x 3 = 1 である • x 1 = 1 または x 2 = 1 または x 4 = 0 である • x 2 = 0 または x 4 = 1 である • x 3 = 1 または x 4 = 1 である まずは具体例から考えてみよう (x 1 , x 2 , x 3 , x 4 ) = (0, 0, 1, 0) → 全条件を満たす (よって答えは Yes)
138. SAT 問題 (充足可能性問題) とは 138 以下の条件をすべて満たす x 1 , x 2 , x 3 (0 か 1 を取る) は存在するか？ • x 1 = 0 である • x 1 = 1 または x 2 = 0 である • x 1 = 1 または x 3 = 0 である • x 2 = 1 または x 3 = 1 である もうひとつの具体例を考えてみよう
139. SAT 問題 (充足可能性問題) とは 139 以下の条件をすべて満たす x 1 , x 2 , x 3 (0 か 1 を取る) は存在するか？ • x 1 = 0 である • x 1 = 1 または x 2 = 0 である • x 1 = 1 または x 3 = 0 である • x 2 = 1 または x 3 = 1 である もうひとつの具体例を考えてみよう (x 1 , x 2 , x 3 ) = (0, 0, 0) → 4 つめの条件を満たさない
140. SAT 問題 (充足可能性問題) とは 140 以下の条件をすべて満たす x 1 , x 2 , x 3 (0 か 1 を取る) は存在するか？ • x 1 = 0 である • x 1 = 1 または x 2 = 0 である • x 1 = 1 または x 3 = 0 である • x 2 = 1 または x 3 = 1 である もうひとつの具体例を考えてみよう (x 1 , x 2 , x 3 ) = (0, 0, 1) → 3 つめの条件を満たさない
141. SAT 問題 (充足可能性問題) とは 141 もうひとつの具体例を考えてみよう (x 1 , x 2 , x 3 ) = (0, 1, 0) → 2 つめの条件を満たさない 以下の条件をすべて満たす x 1 , x 2 , x 3 (0 か 1 を取る) は存在するか？ • x 1 = 0 である • x 1 = 1 または x 2 = 0 である • x 1 = 1 または x 3 = 0 である • x 2 = 1 または x 3 = 1 である
142. SAT 問題 (充足可能性問題) とは 142 もうひとつの具体例を考えてみよう (x 1 , x 2 , x 3 ) = (0, 1, 1) → 2, 3 つめの条件を満たさない 以下の条件をすべて満たす x 1 , x 2 , x 3 (0 か 1 を取る) は存在するか？ • x 1 = 0 である • x 1 = 1 または x 2 = 0 である • x 1 = 1 または x 3 = 0 である • x 2 = 1 または x 3 = 1 である
143. SAT 問題 (充足可能性問題) とは 143 もうひとつの具体例を考えてみよう (x 1 , x 2 , x 3 ) = (1, 0, 0) → 1, 4 つめの条件を満たさない 以下の条件をすべて満たす x 1 , x 2 , x 3 (0 か 1 を取る) は存在するか？ • x 1 = 0 である • x 1 = 1 または x 2 = 0 である • x 1 = 1 または x 3 = 0 である • x 2 = 1 または x 3 = 1 である
144. SAT 問題 (充足可能性問題) とは 144 もうひとつの具体例を考えてみよう (x 1 , x 2 , x 3 ) = (1, 0, 1) → 1 つめの条件を満たさない 以下の条件をすべて満たす x 1 , x 2 , x 3 (0 か 1 を取る) は存在するか？ • x 1 = 0 である • x 1 = 1 または x 2 = 0 である • x 1 = 1 または x 3 = 0 である • x 2 = 1 または x 3 = 1 である
145. SAT 問題 (充足可能性問題) とは 145 もうひとつの具体例を考えてみよう (x 1 , x 2 , x 3 ) = (1, 1, 0) → 1 つめの条件を満たさない 以下の条件をすべて満たす x 1 , x 2 , x 3 (0 か 1 を取る) は存在するか？ • x 1 = 0 である • x 1 = 1 または x 2 = 0 である • x 1 = 1 または x 3 = 0 である • x 2 = 1 または x 3 = 1 である
146. SAT 問題 (充足可能性問題) とは 146 もうひとつの具体例を考えてみよう (x 1 , x 2 , x 3 ) = (1, 1, 1) → 1 つめの条件を満たさない (x 1 , x 2 , x 3 ) = (1, 1, 1) →どの組み合わせでもダメなので答えは No 以下の条件をすべて満たす x 1 , x 2 , x 3 (0 か 1 を取る) は存在するか？ • x 1 = 0 である • x 1 = 1 または x 2 = 0 である • x 1 = 1 または x 3 = 0 である • x 2 = 1 または x 3 = 1 である
147. • このように、SAT 問題はいくつかの条件が与えられて、それを全部 満たすような (x 1 , x 2 , …, x n ) があるかを判定する問題 • ここで x 1 , x 2 , …, x n は 0 か 1 の値を取る • 条件は以下のように「または」で表される SAT 問題 (充足可能性問題) とは 147 x i = または x j = または x k = または x l =
148. 3SAT 問題とは 148 特に、3SAT 問題は全部の条件について 3 個の等式からなる問題を指す (※ 4.3 節で出てきます) 通常の SAT の例 3SAT の例 • x 1 = 0 または x 2 = 0 または x 3 = 1 • x 1 = 1 または x 2 = 1 • x 2 = 0 • x 1 = 0 または x 2 = 0 または x 3 = 1 • x 1 = 1 または x 3 = 1 または x 5 = 1 • x 2 = 1 または x 5 = 0 または x 6 = 1
149. 4.1 4.2 4.3 4.4 P≠NP でわかること 証明のアイデア 二等分問題が NP 完全である証明 諦めるしかないのか？
150. 本節の内容 150 問題 合計が等しくなるように、N 個の整数を 2 分割することは可能か？ 20 35 45 60 20 60 35 45 本節では具体例として、以下の二等分問題が NP 完全であること を証明する
151. 本節の内容 151 今回の証明は以下のように進む 0 1 2 3 Cook-Levin の定理より、SAT 問題が NP 完全 SAT 問題を 3SAT 問題に多項式時間帰着する 3SAT 問題を部分和問題に多項式時間帰着する 部分和問題を二等分問題に多項式時間帰着する ※本スライドの中で最も難しい部分なので、読み飛ばしてもよい (特に段階 2 がとても難しい！)
152. 第 4 章 P ≠ NP の場合に起こること 152 段階 1 段階 2 段階 3 SAT → 3SAT の帰着 3SAT → 部分和問題の帰着 部分和問題 → 二等分問題の帰着
153. 段階 1: SAT → 3SAT の帰着 153 SAT には等式の数が 1 個の条件、2 個の条件、3 個の条件など 様々あるが、まずは 2 個の場合を考える 2 個の場合、変数を 1 個追加して以下のように置き換える • x 1 = a または x 2 = b • x 1 = a または x 2 = b または y = 0 • x 1 = a または x 2 = b または y = 1 (をすべて満たす) 3SAT に 変換 ステップ 1
154. 段階 1: SAT → 3SAT の帰着 154 SAT には等式の数が 1 個の条件、2 個の条件、3 個の条件など 様々あるが、まずは 2 個の場合を考える 2 個の場合、変数を 1 個追加して以下のように置き換える • x 1 = a または x 2 = b 3SAT に 変換 なぜ正しく変換できているか？ → y が 0 か 1 かにかかわらず x 1 = a または x 2 = b が成り立つ時のみ 全条件を満たすため ステップ 1 • x 1 = a または x 2 = b または y = 0 • x 1 = a または x 2 = b または y = 1 (をすべて満たす)
155. 段階 1: SAT → 3SAT の帰着 155 次に、等式の数が 1 個の場合 変数 y 1 , y 2 を追加して以下のように置き換える • x 1 = a • x 1 = a または y 1 = 0 または y 2 = 0 • x 1 = a または y 1 = 0 または y 2 = 1 • x 1 = a または y 1 = 1 または y 2 = 0 • x 1 = a または y 1 = 1 または y 2 = 1 (をすべて満たす) ステップ 2 3SAT に 変換
156. 段階 1: SAT → 3SAT の帰着 156 次に、等式の数が 1 個の場合 変数 y 1 , y 2 を追加して以下のように置き換える • x 1 = a 3SAT に 変換 なぜ正しく変換できているか？ → (y 1 , y 2 ) が 4 通りのどれであっても x 1 = a の時のみ全条件を満たすため ステップ 2 • x 1 = a または y 1 = 0 または y 2 = 0 • x 1 = a または y 1 = 0 または y 2 = 1 • x 1 = a または y 1 = 1 または y 2 = 0 • x 1 = a または y 1 = 1 または y 2 = 1 (をすべて満たす)
157. 段階 1: SAT → 3SAT の帰着 157 次に、等式の数が 3 個の場合 元々から 3SAT の条件を満たしているので何もしない • x 1 = a または x 2 = b または x 3 = c • x 1 = a または x 2 = b または x 3 = c ステップ 3 3SAT に 変換
158. 段階 1: SAT → 3SAT の帰着 158 次に、等式の数が 4 個の場合 新たな変数 y を追加して以下のように置き換える • x 1 = a または x 2 = b または x 3 = c または x 4 = d • x 1 = a または x 2 = b または y = 0 • y = 1 または x 3 = c または x 4 = d (をすべて満たす) ステップ 4 3SAT に 変換
159. 段階 1: SAT → 3SAT の帰着 159 次に、等式の数が 4 個の場合 新たな変数 y を追加して以下のように置き換える • x 1 = a または x 2 = b または x 3 = c または x 4 = d 3SAT に 変換 なぜ正しく変換できているのか？ x 1 = a または x 2 = b の時 y = 1 そうでない時 y = 0 とすれば 4 つの等式のどれかが成立の時のみ全条件を満たすから ステップ 4 • x 1 = a または x 2 = b または y = 0 • y = 1 または x 3 = c または x 4 = d (をすべて満たす)
160. 段階 1: SAT → 3SAT の帰着 160 次に、等式の数が 5 個の場合 新たな変数 y 1 , y 2 を追加して以下のように置き換える • x 1 = a または x 2 = b または x 3 = c または x 4 = d または x 5 = e • x 1 = a または x 2 = b または y 1 = 0 • y 1 = 1 または x 3 = c または y 2 = 0 • y 2 = 1 または x 4 = d または x 5 = e (をすべて満たす) ステップ 5 3SAT に 変換
161. 段階 1: SAT → 3SAT の帰着 161 次に、等式の数が 6 個の場合 新たな変数 y 1 , y 2 , y 3 を追加して以下のように置き換える (7 個以上の場合も同様) • x 1 = a または x 2 = b または x 3 = c または x 4 = d または x 5 = e また は x 6 = f • x 1 = a または x 2 = b または y 1 = 0 • y 1 = 1 または x 3 = c または y 2 = 0 • y 2 = 1 または x 4 = d または y 3 = 0 • y 3 = 1 または x 5 = e または x 6 = f (をすべて満たす) ステップ 6 3SAT に 変換
162. 第 4 章 P ≠ NP の場合に起こること 162 段階 1 段階 2 段階 3 SAT → 3SAT の帰着 3SAT → 部分和問題の帰着 部分和問題 → 二等分問題の帰着
163. 段階 2: 3SAT → 部分和問題の帰着 163 ステップ 0 まずは具体例から考える 左の 3SAT を等価な部分和に変換するにはどうする？ 3SAT 問題 x 1 = 0 または x 2 = 0 または x 3 = 0 1 x 1 = 1 または x 2 = 0 または x 3 = 1 2 x 1 = 1 または x 2 = 1 または x 3 = 0 3
164. 段階 2: 3SAT → 部分和問題の帰着 164 ステップ 1 まず、x 1 = 0 などの各等式が満たされたとき どの条件が直ちに満たされるかについて表を書くことを考える 3SAT 問題 x 1 = 0 または x 2 = 0 または x 3 = 0 1 x 1 = 1 または x 2 = 0 または x 3 = 1 2 x 1 = 1 または x 2 = 1 または x 3 = 0 3 表 条件1 条件2 条件3 x 1 = 0 の場合 x 1 = 1 の場合 x 2 = 0 の場合 x 2 = 1 の場合 x 3 = 0 の場合 x 3 = 1 の場合
165. 段階 2: 3SAT → 部分和問題の帰着 165 ステップ 1A x 1 = 0 のとき、条件 1 が直ちに満たされる 3SAT 問題 x 1 = 0 または x 2 = 0 または x 3 = 0 1 x 1 = 1 または x 2 = 0 または x 3 = 1 2 x 1 = 1 または x 2 = 1 または x 3 = 0 3 表 条件1 条件2 条件3 x 1 = 0 の場合 〇 × × x 1 = 1 の場合 x 2 = 0 の場合 x 2 = 1 の場合 x 3 = 0 の場合 x 3 = 1 の場合
166. 段階 2: 3SAT → 部分和問題の帰着 166 ステップ 1B x 1 = 1 のとき、条件 2, 3 が直ちに満たされる 3SAT 問題 x 1 = 0 または x 2 = 0 または x 3 = 0 1 x 1 = 1 または x 2 = 0 または x 3 = 1 2 x 1 = 1 または x 2 = 1 または x 3 = 0 3 表 条件1 条件2 条件3 x 1 = 0 の場合 〇 × × x 1 = 1 の場合 × 〇 〇 x 2 = 0 の場合 x 2 = 1 の場合 x 3 = 0 の場合 x 3 = 1 の場合
167. 段階 2: 3SAT → 部分和問題の帰着 167 ステップ 1C x 2 = 0 のとき、条件 1, 2 が直ちに満たされる 3SAT 問題 x 1 = 0 または x 2 = 0 または x 3 = 0 1 x 1 = 1 または x 2 = 0 または x 3 = 1 2 x 1 = 1 または x 2 = 1 または x 3 = 0 3 表 条件1 条件2 条件3 x 1 = 0 の場合 〇 × × x 1 = 1 の場合 × 〇 〇 x 2 = 0 の場合 〇 〇 × x 2 = 1 の場合 x 3 = 0 の場合 x 3 = 1 の場合
168. 段階 2: 3SAT → 部分和問題の帰着 168 ステップ 1D x 2 = 1 のとき、条件 3 が直ちに満たされる 3SAT 問題 x 1 = 0 または x 2 = 0 または x 3 = 0 1 x 1 = 1 または x 2 = 0 または x 3 = 1 2 x 1 = 1 または x 2 = 1 または x 3 = 0 3 表 条件1 条件2 条件3 x 1 = 0 の場合 〇 × × x 1 = 1 の場合 × 〇 〇 x 2 = 0 の場合 〇 〇 × x 2 = 1 の場合 × × 〇 x 3 = 0 の場合 x 3 = 1 の場合
169. 段階 2: 3SAT → 部分和問題の帰着 169 ステップ 1E x 3 = 0 のとき、条件 1, 3 が直ちに満たされる 3SAT 問題 x 1 = 0 または x 2 = 0 または x 3 = 0 1 x 1 = 1 または x 2 = 0 または x 3 = 1 2 x 1 = 1 または x 2 = 1 または x 3 = 0 3 表 条件1 条件2 条件3 x 1 = 0 の場合 〇 × × x 1 = 1 の場合 × 〇 〇 x 2 = 0 の場合 〇 〇 × x 2 = 1 の場合 × × 〇 x 3 = 0 の場合 〇 × 〇 x 3 = 1 の場合
170. 段階 2: 3SAT → 部分和問題の帰着 170 ステップ 1F x 3 = 1 のとき、条件 2 が直ちに満たされる 3SAT 問題 x 1 = 0 または x 2 = 0 または x 3 = 0 1 x 1 = 1 または x 2 = 0 または x 3 = 1 2 x 1 = 1 または x 2 = 1 または x 3 = 0 3 表 条件1 条件2 条件3 x 1 = 0 の場合 〇 × × x 1 = 1 の場合 × 〇 〇 x 2 = 0 の場合 〇 〇 × x 2 = 1 の場合 × × 〇 x 3 = 0 の場合 〇 × 〇 x 3 = 1 の場合 × 〇 ×
171. 段階 2: 3SAT → 部分和問題の帰着 171 ステップ 2 そこで、表を部分和問題の数字に変換することを考える 最初の 3 桁を x 1 , x 2 , x 3 に、次の 3 桁を条件 1, 2, 3 に対応させる 部分和問題 100100 x 1 と条件 1 のみを 1 にする (丸が付いているのは条件 1 のみ) 表 条件1 条件2 条件3 x 1 = 0 の場合 〇 × × x 1 = 1 の場合 × 〇 〇 x 2 = 0 の場合 〇 〇 × x 2 = 1 の場合 × × 〇 x 3 = 0 の場合 〇 × 〇 x 3 = 1 の場合 × 〇 ×
172. 段階 2: 3SAT → 部分和問題の帰着 172 そこで、表を部分和問題の数字に変換することを考える 最初の 3 桁を x 1 , x 2 , x 3 に、次の 3 桁を条件 1, 2, 3 に対応させる 部分和問題 100100 x 1 と条件 2, 3 のみを 1 にする (丸が付いているのは条件 2, 3) 100011 表 条件1 条件2 条件3 x 1 = 0 の場合 〇 × × x 1 = 1 の場合 × 〇 〇 x 2 = 0 の場合 〇 〇 × x 2 = 1 の場合 × × 〇 x 3 = 0 の場合 〇 × 〇 x 3 = 1 の場合 × 〇 × ステップ 2
173. 段階 2: 3SAT → 部分和問題の帰着 173 そこで、表を部分和問題の数字に変換することを考える 最初の 3 桁を x 1 , x 2 , x 3 に、次の 3 桁を条件 1, 2, 3 に対応させる 部分和問題 100100 x 2 と条件 1, 2 のみを 1 にする (丸が付いているのは条件 1, 2) 100011 010110 表 条件1 条件2 条件3 x 1 = 0 の場合 〇 × × x 1 = 1 の場合 × 〇 〇 x 2 = 0 の場合 〇 〇 × x 2 = 1 の場合 × × 〇 x 3 = 0 の場合 〇 × 〇 x 3 = 1 の場合 × 〇 × ステップ 2
174. 段階 2: 3SAT → 部分和問題の帰着 174 そこで、表を部分和問題の数字に変換することを考える 最初の 3 桁を x 1 , x 2 , x 3 に、次の 3 桁を条件 1, 2, 3 に対応させる 部分和問題 100100 100011 010110 010001 001101 001010 ステップ 2 表 条件1 条件2 条件3 x 1 = 0 の場合 〇 × × x 1 = 1 の場合 × 〇 〇 x 2 = 0 の場合 〇 〇 × x 2 = 1 の場合 × × 〇 x 3 = 0 の場合 〇 × 〇 x 3 = 1 の場合 × 〇 ×
175. 段階 2: 3SAT → 部分和問題の帰着 175 ステップ 3 すると、部分和問題の合計が 111??? (? は 1 以上 3 以下)※ になることと、3SAT の答えが Yes になることは同じ 部分和問題 合計が 111??? になるように選べるか？ (? は 1～3) ※ 3 つの ? は違う数でもよい 表 条件1 条件2 条件3 x 1 = 0 の場合 〇 × × x 1 = 1 の場合 × 〇 〇 x 2 = 0 の場合 〇 〇 × x 2 = 1 の場合 × × 〇 x 3 = 0 の場合 〇 × 〇 x 3 = 1 の場合 × 〇 × 100100 100011 010110 010001 001101 001010
176. 段階 2: 3SAT → 部分和問題の帰着 176 なぜか？
177. 段階 2: 3SAT → 部分和問題の帰着 177 理由 部分和問題 100100 100011 010110 010001 001101 001010 片方だけを選ぶ 合計を 111??? にする必要があるが、上から 1 桁目を 1 にするには 1, 2 個目の片方だけを選ぶ必要がある (※これは値 x 1 を決めることに対応) 表 条件1 条件2 条件3 x 1 = 0 の場合 〇 × × x 1 = 1 の場合 × 〇 〇 x 2 = 0 の場合 〇 〇 × x 2 = 1 の場合 × × 〇 x 3 = 0 の場合 〇 × 〇 x 3 = 1 の場合 × 〇 ×
178. 段階 2: 3SAT → 部分和問題の帰着 178 理由 同様に、上から 2 桁目を 1 にするには 3, 4 個目の片方だけを選ぶ必要がある (※これは値 x 2 を決めることに対応) 部分和問題 100100 100011 010110 010001 001101 001010 片方だけを選ぶ 表 条件1 条件2 条件3 x 1 = 0 の場合 〇 × × x 1 = 1 の場合 × 〇 〇 x 2 = 0 の場合 〇 〇 × x 2 = 1 の場合 × × 〇 x 3 = 0 の場合 〇 × 〇 x 3 = 1 の場合 × 〇 × 片方だけを選ぶ
179. 段階 2: 3SAT → 部分和問題の帰着 179 理由 部分和問題 100100 100011 010110 010001 001101 001010 片方だけを選ぶ 同様に、上から 3 桁目を 1 にするには 5, 6 個目の片方だけを選ぶ必要がある (※これは値 x 3 を決めることに対応) 片方だけを選ぶ 片方だけを選ぶ 表 条件1 条件2 条件3 x 1 = 0 の場合 〇 × × x 1 = 1 の場合 × 〇 〇 x 2 = 0 の場合 〇 〇 × x 2 = 1 の場合 × × 〇 x 3 = 0 の場合 〇 × 〇 x 3 = 1 の場合 × 〇 ×
180. 段階 2: 3SAT → 部分和問題の帰着 180 理由 部分和問題 100100 100011 片方だけを選ぶ 010110 010001 001101 001010 片方だけを選ぶ 片方だけを選ぶ 次に、合計 111??? の最初の ? を 1 以上にするには 条件 1 を満たすような x 1 , x 2 , x 3 の選択を一回は行わなければならない 最低 1 個の “1” を選ぶ 表 条件1 条件2 条件3 x 1 = 0 の場合 〇 × × x 1 = 1 の場合 × 〇 〇 x 2 = 0 の場合 〇 〇 × x 2 = 1 の場合 × × 〇 x 3 = 0 の場合 〇 × 〇 x 3 = 1 の場合 × 〇 ×
181. 段階 2: 3SAT → 部分和問題の帰着 181 理由 部分和問題 100100 100011 片方だけを選ぶ 010110 010001 001101 001010 片方だけを選ぶ 片方だけを選ぶ 同様に、合計 111??? の中央の ? を 1 以上にするには 条件 2 を満たすような x 1 , x 2 , x 3 の選択を一回は行わなければならない 最低 1 個の “1” を選ぶ 表 条件1 条件2 条件3 x 1 = 0 の場合 〇 × × x 1 = 1 の場合 × 〇 〇 x 2 = 0 の場合 〇 〇 × x 2 = 1 の場合 × × 〇 x 3 = 0 の場合 〇 × 〇 x 3 = 1 の場合 × 〇 ×
182. 段階 2: 3SAT → 部分和問題の帰着 182 理由 部分和問題 100100 100011 片方だけを選ぶ 010110 010001 001101 001010 片方だけを選ぶ 片方だけを選ぶ 同様に、合計 111??? の最後の ? を 1 以上にするには 条件 3 を満たすような x 1 , x 2 , x 3 の選択を一回は行わなければならない 最低 1 個の “1” を選ぶ 表 条件1 条件2 条件3 x 1 = 0 の場合 〇 × × x 1 = 1 の場合 × 〇 〇 x 2 = 0 の場合 〇 〇 × x 2 = 1 の場合 × × 〇 x 3 = 0 の場合 〇 × 〇 x 3 = 1 の場合 × 〇 ×
183. 段階 2: 3SAT → 部分和問題の帰着 183 理由 部分和問題 したがって、合計が 111??? (? は 1 以上) になるように選べることと 3SAT において、全条件を満たす (x 1 , x 2 , x 3 ) があることは同じ 合計が 111??? になるように選べるか？ (? は 1 以上) 100100 100011 010110 010001 001101 001010 表 条件1 条件2 条件3 x 1 = 0 の場合 〇 × × x 1 = 1 の場合 × 〇 〇 x 2 = 0 の場合 〇 〇 × x 2 = 1 の場合 × × 〇 x 3 = 0 の場合 〇 × 〇 x 3 = 1 の場合 × 〇 ×
184. 段階 2: 3SAT → 部分和問題の帰着 184 補足 部分和問題 ここで、各条件は 3 つの等式で成り立っているので どういう選び方をしても、下 3 桁が 4 以上になることは絶対にない 100100 100011 010110 010001 001101 001010 合計が 111??? になるように選べるか？ (? は 1 以上 / かつ 3 以下 であると考えてもよい) 表 条件1 条件2 条件3 x 1 = 0 の場合 〇 × × x 1 = 1 の場合 × 〇 〇 x 2 = 0 の場合 〇 〇 × x 2 = 1 の場合 × × 〇 x 3 = 0 の場合 〇 × 〇 x 3 = 1 の場合 × 〇 ×
185. 段階 2: 3SAT → 部分和問題の帰着 185 しかし、今回取り上げた部分和問題では… 合計が 111??? (? は 1 以上 3 以下) と 変えられる設定になっており 実際の部分和問題とは少し違う※ ※実際の部分和問題では、合計が 111123 といったように合計を 1 つに決める必要がある
186. 段階 2: 3SAT → 部分和問題の帰着 186 ステップ 4 そこで、調整項 000100, 000010, 000001 を 2 個ずつ足すと 合計を 111333 にできますか？ という部分和問題に帰着できる 部分和問題もどき 合計を 111??? にできるか？ (? は 1～3) 部分和問題 100100 100011 010110 010001 001101 001010 000100 000100 000010 000010 000001 000001 合計を 111333 にできるか？ 変換 100100 100011 010110 010001 001101 001010
187. 段階 2: 3SAT → 部分和問題の帰着 187 したがって、3SAT を部分和問題に 多項式時間帰着することができる (今回は一例しか扱わなかったが、他のケースでも成り立つ)
188. 第 4 章 P ≠ NP の場合に起こること 188 段階 1 段階 2 段階 3 SAT → 3SAT の帰着 3SAT → 部分和問題の帰着 部分和問題 → 二等分問題の帰着
189. 段階 3: 部分和問題 → 二等分問題の帰着 189 今回も具体例から考える 左の部分和問題を二等分問題に変換するにはどうする？ 部分和問題 20 30 40 50 70 合計を 100 にできるか？ 二等分問題 ?
190. 段階 3: 部分和問題 → 二等分問題の帰着 190 部分和問題 20 30 40 50 70 合計を 100 にできるか？ 二等分問題 20 30 40 50 70 100 万 100 100 万 110 二等分 できるか？ 実は、右のように「100 万 100」と「100 万 110」の 2 つを追加した部分和問 題に帰着できる → なぜ？
191. 段階 3: 部分和問題 → 二等分問題の帰着 191 部分和問題 20 30 40 50 70 合計を 100 にできるか？ 二等分問題 20 30 40 50 70 100 万 100 100 万 110 100 万があまりにも大きいので、二等分に成功するには「100 万 100」と「100 万 110」が別グループになるべき したがって、残りの要素を 100 対 110 に分割して帳尻合わせする必要がある 絶対に 別グループ
192. 段階 3: 部分和問題 → 二等分問題の帰着 192 部分和問題 20 30 40 50 70 合計を 100 にできるか？ 二等分問題 20 30 40 50 70 100 万 100 100 万 110 残りの要素を 100 対 110 に分割するということは、20, 30, 40, 50, 70 の中からい くつかを選んで合計を 100 にすることと同じ したがって、左の部分和問題と右の二等分問題の答えは同じ 100 対 110 に分割
193. • 実は他のケースでも、ものすごい大きい数※ を 2 つ追加して、 残りの数の分割 (何対何に分けるべきか) を強制的に決めるよ うにすると、変換できる • したがって、部分和問題は二等分問題に多項式時間帰着可能 段階 3: 部分和問題 → 二等分問題の帰着 193 ※全要素の合計以上であればよい
194. 結論 194 これで SAT → 3SAT → 部分和問題 → 二等分問題の帰着に成功 したがって、二等分問題は NP 完全！ 部分和問題 二等分問題 20 30 40 50 20 50 30 40 3SAT 問題 or or or or or or SAT 問題 or or or 20 30 40 50 100
195. 結論 195 そして、他の様々な NP 問題についても 同じような方法で NP 完全であることが証明できる ハミルトン閉路問題 巡回セールスマン問題 部分和問題 二等分問題 最大独立集合問題 最小頂点被覆問題 ナップザック問題 SAT 問題 グラフ彩色問題 ビンパッキング問題 テトリス 数独
196. • (判定版ではない普通の) 巡回セールスマ ン問題※ のように、「明らかに NP 完全 の問題と同程度以上に難しいが NP では ない問題」もいくつか存在する • このような問題のことを NP 困難という • NP 困難は NP 完全を含むことに注意 重要な補足 196 NP 完全 NP 困難 ※巡回セールスマン問題は p.77 を参照
197. 4.1 4.2 4.3 4.4 P≠NP でわかること 証明のアイデア 二等分問題が NP 完全である証明 諦めるしかないのか？
198. 分岐点 198 もし P ≠ NP ならば、二等分問題を含む多数の問題が 多項式時間で解けないということになる こういう問題を N = 100, N = 1000 など 大きいサイズで解くのは諦めるしかないのか？
199. 第 4 章 P ≠ NP の場合に起こること 199 対処法 1 対処法 2 対処法 3 入力の 性質を使う 指数時間の 中で頑張る 近似解を 目指す
200. 対処法 1: 入力の性質を使う • 問題によっては、入力の性質を使うと N が大きくても解ける 場合がある • たとえば部分和問題 (→ p.71) の場合、合計 S が 1000～1 万な ど十分小さい場合、動的計画法 (次ページで例を説明) によっ て一瞬で答えを計算できる 200
201. 具体例 201 2, 3, 4 の中から何個か 選んで合計を S = 6 に することは可能か？ 右図のように「◇番目までの 数を使って合計を△にできる か？」の表を作っていくこと を考える 例 0 1 2 3 4 5 6 合計 0 番目まで 1 番目まで 2 番目まで 3 番目まで
202. 具体例 202 2, 3, 5 の中から何個か 選んで合計を S = 6 に することは可能か？ 右図のように「◇番目までの 数を使って合計を△にできる か？」の表を作っていくこと を考える 例 0 1 2 3 4 5 6 〇 × × × × × × 合計 0 番目まで 1 番目まで 2 番目まで 3 番目まで 0 番目までの場合 当然合計 0 しかできない
203. 具体例 203 2, 3, 5 の中から何個か 選んで合計を S = 6 に することは可能か？ 右図のように「◇番目までの 数を使って合計を△にできる か？」の表を作っていくこと を考える 例 0 1 2 3 4 5 6 〇 × × × × × × 合計 0 番目まで 〇 × 〇 × × × × 1 番目まで 2 番目まで 3 番目まで 1 番目の数は 2 使わない (1 番目の数を) 使う
204. 具体例 204 2, 3, 5 の中から何個か 選んで合計を S = 6 に することは可能か？ 右図のように「◇番目までの 数を使って合計を△にできる か？」の表を作っていくこと を考える 例 0 1 2 3 4 5 6 〇 × × × × × × 合計 0 番目まで 〇 × 〇 × × × × 1 番目まで 〇 × 〇 〇 × 〇 × 2 番目まで 3 番目まで 2 番目の数は 3 使わない (2 番目を) 使う
205. 具体例 205 2, 3, 5 の中から何個か 選んで合計を S = 6 に することは可能か？ 右図のように「◇番目までの 数を使って合計を△にできる か？」の表を作っていくこと を考える 例 0 1 2 3 4 5 6 〇 × × × × × × 合計 0 番目まで 〇 × 〇 × × × × 1 番目まで 〇 × 〇 〇 × 〇 × 2 番目まで 〇 × 〇 〇 × 〇 × 3 番目まで 3 番目の数は 5 使わない 使 う
206. • S = 6 の部分はバツになっているため、答えが No だとわかる • このように、表を順番に埋めていくような手法を動的計画法と いうが、この方法を使うと (カードの枚数 N) × (合計 S) くらい の計算量で解ける • つまり、S が 1 万程度であれば、N = 1000 などの大きい入力で も現実的な時間で解ける！※ 具体例 206 ※もちろん、S が大きい時に解けていない以上、部分和問題が (入力長に対する) 指数時間であることには変わりない
207. 第 4 章 P ≠ NP の場合に起こること 207 対処法 1 対処法 2 対処法 3 入力の 性質を使う 指数時間の 中で頑張る 近似解を 目指す
208. 対処法 2: 指数時間の中で頑張る • 同じ指数時間でも、計算量の改善によって大幅に実行時間が短 くなることがある (たとえば O(2n) → O(2n/2) の改善で、n = 60 程度の規模の問題が一気に現実的になる) • さらに、不要な探索をしない枝刈りという手法を使うと、見た 目の計算量より圧倒的に速く動作することがある (場合によっ ては n = 100～200 でも十分チャンスあり) 208
209. 枝刈りの例 209 70, 50, 30, 20 の中からいくつか選び、合計を 80 にする方法はあるか？ 例として、以下の部分和問題を考える 70 50 30 20
210. 枝刈りの例 210 もし全通りを樹形図のように調べると、何通り調べる必要があるか？ 合計0
211. 枝刈りの例 211 もし全通りを樹形図のように調べると、何通り調べる必要があるか？ 合計0 合計70 合計0
212. 枝刈りの例 212 もし全通りを樹形図のように調べると、何通り調べる必要があるか？ 合計0 合計50 合計70 合計120 合計0 合計70 合計0 2 枚目 (50) を 選ばない 選ぶ
213. 枝刈りの例 213 もし全通りを樹形図のように調べると、何通り調べる必要があるか？ 合計0 合計30 合計50 合計80 合計70 合計100 合計120 合計150 合計0 合計50 合計70 合計120 合計0 合計70 合計0 選ぶ 3 枚目 (30) を 選ばない
214. 枝刈りの例 214 合計 0 合計 20 合計 30 合計 50 合計 50 合計 70 合計 80 合計 100 合計 70 合計 90 合計 100 合計 120 合計 120 合計 140 合計 150 合計 170 もし全通りを樹形図のように調べると、何通り調べる必要があるか？ → 全部で 24 = 16 通り！ 合計0 合計30 合計50 合計80 合計70 合計100 合計120 合計150 合計0 合計50 合計70 合計120 合計0 合計70 合計0 選ぶ 4 枚目 (20) を 選ばない
215. 枝刈りの例 215 しかし、合計が 80 を超えた瞬間に探索を打ち切ると 10 通りに減る 合計 0 合計 20 合計 30 合計 50 合計 50 合計 70 合計 80 合計 100 合計 70 合計 90 合計0 合計30 合計50 合計80 合計70 合計100 合計0 合計50 合計70 合計120 合計0 合計70 合計0 選ぶ
216. • 今回は n = 4 と小さかったので 16 通り → 10 通りと、2 倍に満たない 減少にとどまった • しかし、n = 50 などの場合、探索パターン数が数億分の 1 など大幅に 減少することもある 枝刈りの例: 補足 216 注意 もちろん、意地悪なケース※ では前述の枝刈りが通用しないため「計算量が O(2n) から O(2n/2) に減った」のような理論的な改善にはならない。しかし現実のケース で問題を解くときは、多くの場合に枝刈りが通用することがある。 ※例: 前述の部分和問題で、S が全部の数の合計に非常に近い場合 (ほぼ探索の打ち切りが行われない)
217. 第 4 章 P ≠ NP の場合に起こること 217 対処法 1 対処法 2 対処法 3 入力の 性質を使う 指数時間の 中で頑張る 近似解を 目指す
218. 対処法 3: 近似解を目指す 218 これまでは、左図のような「正確に判定する問題」を考えてきた しかし実際は、右図のように「できるだけ近づける」で十分なこともある N 個の整数がある。 合計が完全に等しくな るように 2 グループに 分けることは可能か？ 二等分問題 二等分問題・改 N 個の整数がある。 合計ができるだけ等し くなるように 2 グルー プに分割せよ。
219. 対処法 3: 近似解を目指す 219 それでは、正確な「判定」は無理でも、たとえば 1.05 倍以内の差にすること を目標にすれば行けるのでは？ (このようなことを “近似解を出す” という) 例として、二等分問題の以下のケースを考える 123, 158, 241, 316, 339, 372 を、できるだけ合計が等しくなるように 2 つに分けることは可能か？ 123 158 241 316 339 415
220. 近似解を目指す例 220 1 つの方法として、合計が近くなるような交換を 改善できなくなるまで繰り返す方法がある (山登り法と呼ばれる手法) 123 158 241 316 339 415 合計 522 合計 1070 初期段階
221. 近似解を目指す例 221 1 つの方法として、合計が近くなるような交換を 改善できなくなるまで繰り返す方法がある (山登り法と呼ばれる手法) 123 158 241 316 339 415 合計 522 合計 1070 ステップ 1 この 2 個を交換すればよいのでは？
222. 近似解を目指す例 222 1 つの方法として、合計が近くなるような交換を 改善できなくなるまで繰り返す方法がある (山登り法と呼ばれる手法) 合計 703 合計 889 ステップ 1 123 339 241 316 158 415
223. 近似解を目指す例 223 1 つの方法として、合計が近くなるような交換を 改善できなくなるまで繰り返す方法がある (山登り法と呼ばれる手法) 合計 703 合計 889 ステップ 2 123 339 241 316 158 415 この 2 個を交換すればよいのでは？
224. 近似解を目指す例 224 1 つの方法として、合計が近くなるような交換を 改善できなくなるまで繰り返す方法がある (山登り法と呼ばれる手法) 合計 778 合計 814 ステップ 2 123 339 316 241 158 415
225. • 今回の例の場合、たった 2 ステップで 778 対 814 という「かなり 良い近似解」を得ることができた※ • そして実は、n2 ステップ程度計算すれば、ほほすべてのケースでか なり良い近似解をを得られることが知られている • このように、厳密な最適解を得るのが無理でも、近似解であれば可 能かもしれない 近似解を目指す例 225 ※ちなみに、最適解 (一番良い解) は 779 対 813
226. • 近似解を得る方法の中には、「どのようなケースでも最適解の 2 倍 以内になることが保証できる」ような方法も存在する • このような方法を (性能保証付き) 近似アルゴリズムという※ • また、必ず 2 倍以内に近似できることを 2-近似、必ず 1.5 倍以内に 近似できることを 1.5-近似という (他の倍数の場合も同様) 近似解を目指す: 補足 226 ※性能保証付き近似アルゴリズムのみを「近似アルゴリズム」と言う場合もある
227. 第 5 章 おわりに
228. 本講演のまとめ (1/3) • 計算量が O(n2) や O(n3) など入力長 n の多項式で表される場合、多 項式時間であるという。逆に O(2n) などになってしまう場合、指数 時間という。 • NP 問題とは、多項式時間で検証可能な判定問題のことを指し、部 分和問題など多数の問題が該当する。 • P 対 NP 問題とは、果たしてすべての NP 問題が多項式時間で解け るのか、という問題である。 228
229. 本講演のまとめ (2/3) 229 そして、結論が P = NP でも P ≠ NP でも アルゴリズムの世界に大きな影響を及ぼすことになる P = NP の場合 P ≠ NP の場合 暗号の安全性が根本から崩れる 部分和問題を含む多数の問題が全部 多項式時間で解くのが不可能だとわかる
230. 本講演のまとめ (3/3) 230 また「NP 問題で最強」が証明されている「NP 完全」の問題がある したがって、P 対 NP 問題は これらが多項式時間で解けるかどうかを証明するだけで解ける ハミルトン閉路問題 巡回セールスマン問題 部分和問題 二等分問題 最大独立集合問題 最小頂点被覆問題 ナップザック問題 SAT 問題 グラフ彩色問題 ビンパッキング問題 テトリス 数独
231. 第 5 章 おわりに 231 皆さん、P 対 NP 問題の 世界はどうでしたか？
232. • P 対 NP 問題はとても理解が難しいトピックです (東大の情報科学 科でも学部 3 年の後期で学びます) • 本スライドも少し難しかったかもしれませんが、少しでも理解して いただけたら幸いです おわりに 232
233. 1. 米田優峻、『問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく 本』、技術評論社 (2022) 2. Michael Sipser、『計算理論の基礎 [原著第 3 版] 2. 計算可能性の理論』、共立出版 (2023) 3. Michael Sipser、『計算理論の基礎 [原著第 3 版] 3. 複雑さの理論』、共立出版 (2023) 4. J.A.ブーブマン、『暗号理論入門 [原著第 3 版]』、丸善出版 (2012) 5. 梅谷俊治、『しっかり学ぶ数理最適化』、講談社 (2020) 6. https://www.metaculus.com/questions/1408/p-np-is-true/ 参考文献 233
234. 最後までお読みいただき ありがとうございました