ゆる計算理論ラジオ / P vs NP for beginner

Transcript

1. ゆる計算理論ラジオ 2023/03/17 giftee TechBash @megane42
2. クイズ P = NP? P ≠ NP?
3. P = NP だと思った人は ひらめきや創造性を伴う、人間の聖域とも言えるクリエイティブな活動を全て機械で代 替可能だと思ってるってことですよね？
4. 自己紹介 @megane42 趣味: かっこいいワンタイムパスワード集め
5. 背景 どんな施策でも実施できる 柔軟なキャンペー ン設計システムを作りたかった 少し考えた結果、オートマトンというやつに 構造が似ている気がしてきた どんな施策でも実施できる ことを数学的に言 えたりしないだろうか なんかチューリング完全的な？
6. 参考図書 計算理論とオートマトン言語理論 [第2版] 丸岡 章 著
7. 結論 わからなかった 考えていたシステムがチューリングマシ ン（詳細は割愛）に変換可能であること が言えれば、並大抵のキャンペーンは実 施できそうだったが、その証明が困難だ った 一方、その過程で面白い事柄を学べた P 対 NP 問題
8. P 対 NP 問題 P とか NP というのは 問題のクラス （種類）のこと P = NP なのか P ≠ NP なのかで一生揉めている 今のところ P ≠ NP っぽいと思われているが、誰も証明できていない P ⊆ NP であることはわかっている
9. クラス P の定義 答えを効率よく見つけられる問題 ざっくりいうと「しらみつぶしに頑張る」より効率的な手段があるタイプの問題
10. クラス P の例 ソート クイックソートみたいな効率の良いアルゴリズムが存在する 100 冊のマンガを 1 巻から順に並び替えたいときに、「全ての取りうる並び順を洗 い出したあと、順番に並んでいるパターンが見つかるまでしらみつぶしにチェック する」みたいなことはしない
11. クラス NP の定義 答えの検証だけは効率よくできる問題 効率的に解けるかどうかについては触れていないことに注意 まず答えの検証が効率良くできたら、その問題はクラス NP 更に答えの探索が効率良くできたら、その問題はクラス P
12. クラス NP の例 パズル（ハミルトン閉路問題） 与えられたグラフの全点を 1 度ずつ通って最初の点 に戻ってくるような経路は存在するか？ 答えが与えられたら、その答えの検証は簡単にでき るので、クラス NP 今のところ効率よく解く方法は見つかっていない 取りうる経路のパターンを全て列挙してチェッ クするしかない 見つかってないだけで存在するかもしれない
13. P 対 NP 問題 再掲 P = NP ? P ≠ NP ? ハミルトン閉路問題のような NP 問題に対して、効率良い解き方が 存在するけど人類が まだ見つけてないだけなのか (P = NP なのか) どうかが一生わかっていない
14. 身近な NP 身の回りの問題は、実は NP であることが多い 全てのバイトの希望を満たすシフト表の作成 タンパク質の構造の最適化 ロジスティクスの最適化 P = NP が判明すれば、世の中が劇的に変わる（効率が良くなる）
15. 帰着と NP 完全 一般に、ある問題を変形して別の問題に置き換える（帰着させる）ことができる NP 完全 な問題とは、任意の NP 問題をそれに帰着できるような問題のこと NP 問題の母みたいなことです NP 完全問題のうち 1 つでも P であることが証明できると、たちどころに全ての NP が P であることが言える (すなわち P = NP) 実は ハミルトン閉路問題は NP 完全 他にも NP 完全問題がたくさん見つかっている が、そのいずれも効率的なアルゴリズムが一生見つかっていない・・・
16. NP 問題と創造性 (1) 数学の定理の証明 ある定理の証明が与えられたときに、それを検証するのは簡単 NP 問題の定義を満たすので、数学の定理の証明は NP 問題
17. NP 問題と創造性 (2) 良い俳句をつくる ある俳句が与えられたときに、それがグッと来るかどうか検証するのは簡単 NP 問題の定義を満たすので、俳句の作成は NP 問題
18. NP 問題と人間 人間は全パターンを洗い出したりしないけど、正解を見 つけることがある この世の定理全ての組み合わせを列挙したりせずに 定理の証明を思いつく 17 文字の 50 音全ての組み合わせを列挙したりせず に良い俳句を思いつく 人間は ひらめき という神秘的な能力で答えを見つける ことができる もし P = NP だとすると、人間のひらめきに大した価値 が無い気がしてきませんか？
19. まとめ 名前しか知らなかった「P 対 NP 問題」について、解像度が高まった 効率の良い解き方が存在はするけど、人類が見つけられてないだけ？ もし P = NP だった場合、世の中のいろいろな問題が一挙に効率化されてしまう 特に NP 完全問題が狙い目 もし P = NP だった場合、人間の持つ「ひらめき」という神秘的な能力の価値が低くなる 気がする
20. 寄り道: 「効率が良い」の定義 効率が良い ＝ 入力のサイズ n に対して、n の多項式時間で解ける 例: n 冊のマンガを並べ替えたいとき 最低でも n^2 ステップで並べ替えができる方法 → 効率が良い 最低でも 2^n ステップで並べ替えができる方法 → 効率が悪い しらみつぶしに全パターン網羅しようとすると、得てしてパターンは指数関数的に 増えるので、効率が悪い（多分）
21. 寄り道: NP 問題の別の定義 非決定性チューリングマシン で効率良く解ける問題 非決定性チューリングマシンとは、超ざっくりいうと、同じ入力が与えられたとき のふるまいが一意に決まってないような機械のこと 入力: グラフ ふるまい: どの経路に着目するか 各経路 1 つずつの検証は効率良く行える たまたま正解の経路に着目すれば答えが見つかる ありうる全パターンを同時に並列処理できるなら効率良く解ける、みたいなことを 言っている NP は Non-deterministic Polynomial の略で、Not P ではないです
22. 参考 計算下界の解明 ー その意義とシナリオ (徳山 豪) https://researchmap.jp/read0065631/misc/31636571 https://researchmap.jp/read0065631/misc/31636564 第14回　P≠NP予想について考える（前編） (辻真吾) https://www.school.ctc-g.co.jp/python/columns/tsuji/tsuji14.html 第15回　P≠NP予想について考える（後編） (辻真吾) https://www.school.ctc-g.co.jp/python/columns/tsuji/tsuji15.html