笑わない数学 NHK https://www.nhk.jp/p/ts/Y5R676NK92/
放送 NHK総合。全12回。
www.nhk.jp
【※以下ネタバレ】
https://www.nhk.jp/p/ts/Y5R676NK92/
パンサー尾形貴弘が難解な数学の世界を大真面目に解説する異色の知的エンターテインメント番組！ 「リーマン予想」「フェルマーの最終定理」「連続体仮説」「四色問題」「ガロア理論」「abc予想」「確率論」「P対NP問題」「カオス理論」「ポアンカレ予想」「暗号理論」「虚数」・・・。天才数学者をも苦しめてきた数々の難問、そして美しくも不思議な知の世界を、１回３０分ワンテーマ、ギャグ封印で、トコトン分かりやすく掘り下げる！
MC 尾形貴弘 (パンサー)
第４回「Ｐ対ＮＰ問題」(2022年8月3日(水)放送)
内容
笑わない数学「Ｐ対ＮＰ問題」
[総合] 2022年08月03日 午後11:00 ~ 午後11:30 (30分)
パンサー尾形貴弘が数学の難問を大真面目に解説する「笑わない数学」。今回は懸賞金１億円の「Ｐ対ＮＰ問題」。世紀の難問が解けるとき、私たちの暮らしは激変する！？
例えば、遠足のおやつ選び。ナップサックの容量を超えない範囲で、おやつの値段を目標以上にする組み合わせはあるか？「Ｐ対ＮＰ問題」は、無数にある組み合わせをしらみつぶしに調べないと答えが見つからないのか。あるいは、簡単に解けるコツがあるのか、に関する未解決問題だ。医学、経済、戦争…。私たちの暮らしにも関わる様々な問題が、数学で一気に解決する日は来るのか。そこで待っているのはバラ色の世界か、それとも…？
【司会】パンサー尾形
●「Ｐ対ＮＰ問題」とは？
もしここにおやつが40種類あり、お小遣い500円の中でナップサックにおやつを入れるとして、一番価格の合計が高くなる組み合わせはどれか？ 一つ一つ組み合わせを調べていくとして、その数は「１兆９９５億１１６２万７７７６通り」にもなる。
「Ｐ対ＮＰ問題」とは、『こういうタイプの問題は、一つ一つしらみつぶしにして調べないと答えが見つからないのか？ または答えにたどり着けるコツがあるのか？』という問題である。
●もう少し詳しく
Pとは「Polynomial Time」（多項式時間）、「ほどほどの時間」という意味。「簡単に解けるコツがある問題」のこと。
NPとは「Non-deterministic Polynomial time」（非決定性多項式時間）という意味。「簡単に解けるコツが無く、しらみつぶしに調べないといけない時間のかかる問題」のこと。
NP問題の例の一つが「ハミルトン閉路問題」。点同士が線で結ばれた図形で「すべての点を一度だけ通り、元に戻って来る経路は有るか」というもの。この問題は解くコツが無く、全てのパターンをしらみつぶしに調べてみるしかない。
また「巡回セールスマン問題」という問題もNP問題。例えば「セールスマンが営業所を出て、顧客の家四軒を一回ずつ訪ね、そのあと営業所に戻って来る」という場合の、所要時間が最短の経路を見つける問題。家が４軒なら全部で12パターンのため、人が調べることも可能だが、もし訪問先が「５０軒」になったなら、コンピューターで計算しても、組み合わせが多すぎて計算に百億年以上かかってしまう。
●様々なNP問題
NP問題は「巡回セールスマン問題」以外にも、実は身近にたくさんある。例を挙げると
・ナップサック問題 … ナップサックの容量の範囲内で、荷物の価値を目標以上にする組み合わせは有るか？
・スケジューリング問題 … 目標を達成するための、人員や機械の配置方法は有るか？
・分割問題 … たくさんの荷物に対して、重量を均等にする組み合わせは有るか？
●ケーニヒスベルクの橋問題
かつて、ケーニヒスベルクという都市（現ロシア・カリーニングラード）には七つの橋が架かっていたが、「七つの橋を一回だけ渡って全ての橋を渡るルートは有るか？」という事が話題になった。全ての組み合わせは５０４０通りもあり、典型的な「NP問題」に見えたが……
18世紀の大数学者・レオンハルト・オイラーは、ルートを簡略化して点を線で結んだ図形にして、結局この問題は「この図形は一筆書き出来るか？」ということだと看破した。そして一筆書きができる条件は
1)点から出る線の数が偶数
か
2)奇数の点があっても二つだけ
という事を発見した。
つまりケーニヒスベルクの橋問題は、NP問題ではなく、コツがあってすぐに解けるP問題だったのである。ちなみにケーニヒスベルクの橋は一筆書き出来ないので、一回だけ渡って全ての橋を巡ることはできない。
同様に「NP問題と思われていたが実はP問題だった」という例が存在する。ある数が素数かどうかを判定する「素数判定問題」は、2002年に実はコツがあり簡単に判定できるP問題であることが解った。
●重大な発見
1970年代、東西両陣営は対立し、戦いに勝つため、戦力や人員をいかに効率よく配備すればよいかを研究していた。つまりNP問題の一つ「スケジューリング問題」で、東西の数学者は研究を続けていた。そして西側のスティーブン・クックと東側のレオニード・レビンは、それぞれ独立して重大な発見をした。それは
もしある超難しいNP問題一つにコツがあることを証明する（実はP問題だと証明する）事が出来れば、他のありとあらゆるNP問題も全てコツがある（P問題）と言える
という事実だった。
もしNP問題に簡単に解けるコツが見つかれば世の中はどうなるか。医学、運送業界。そして戦争など、ありとあらゆる分野で劇的な進歩が起き、世の中がガラッと変わることになるはずである。ただし、数学者たちは「全てのNP問題にコツがある」という考えには否定的な模様。
