｢P対NP問題｣に隠されたウクライナ危機〜笑わない､いや笑えない数学(第4回)

　例えば､遠足のおやつ選びで､リュックの容量を超えない範囲で､おやつの値段を目標以上にする組合せはあるのか？
　数学が苦手なアナタは､1つ1つ組合せを調べ上げ､夜更しをしてまでおやつの値段を調べ上げるだろうか？
　それとも多少は数学が得意な君なら､おやつの数をXとし､値段をYとし､リュックの容量をZとして､ある簡単な方程式を作って解こうとするのだろうか？
　多分､両者ともにすぐに頓挫するだろうか。
　つまり､難題に直面した時はまずは､”逃げるが勝ち”なのである(多分)。

　往々にして､多めにおやつを持ってくるガキほど､(私がそうであった様に^^;)バスの中でお腹を壊し､最悪はゲロを吐く。
　”数学の巨人”ガウスの名言にある様に､”少量こそが豊熟”(Pauca sed Matura)なのだ。
　つまり､出来ない事を知る事も､それに難解さの程度を知る事も､これまた学習の一つである。

｢P対NP問題｣

　｢P対NP問題｣とは､無数にある組合せを(コンピュータを使って)しらみ潰しに調べないと答えが見つからないのか？いや､それとも簡単に解けるコツがあるのか？に関する未解決問題である。
　私とした事が､｢四色問題｣(第3回)も｢P対NP問題｣(第4回)も見逃してしまった。

　そこで､まずは専門用語の解説からです。
　”P問題”とは､コンピュータで簡単に解ける問題で､”NP問題”とは難しい問題だが(一旦解けてしまえば)検証が容易な問題を指す。
　この”NP問題”の多くは､社会が直面する最も困難かつ緊急な問題であるとされる。
　100万ドルの懸賞金のかかった｢P対NP問題｣とは本質的には､”P問題とNP問題は同じか？”というもの。
　つまり､極めて困難に見える問題も(途方もなく)”速く適切なアルゴリズムを見つけられた場合､それを用いれば妥当な時間で解けるだろうか？”という予想である。
　事実､”P問題は全てNP問題である”事は証明されてるが､その逆である”NP問題は全てP問題の様に素早く解けるか？”という事は(残念ながら)未だに証明されてはいない。
　数学的に記述すれば､P⊂NPは真だがNP⊂Pが真かどうかがわからない。
　つまり､P=NPが真であるかは甚だ疑問で､多くの数学者によれば､P≠NPだろうとされる。故に､｢P対NP問題｣は今では｢P≠NP問題｣とも呼ばれる。

　もしそう(P=NPが真)であれば､多くの難問がいきなり解ける様になる。まさに数学が人類を､いや世界を征する時代が来る。
　例えば､ウクライナ危機だって適切なアルゴリズムを見つけさえすれば､簡単に解決できるのだ。つまり､核も安保理もアメリカやNATOも軍隊すらもいらない。
　逆に｢P対NP問題｣が解けなければ､つまりP≠NPであれば､(コンピュータは勿論)人間の知能には基本的な限界がある事になる。

　結局､これまで様多くの数学者が色んな手法を試みるも､”P=NP”はおろか”P≠NP”も証明できない。これはリーマン予想が証明はおろか､反例すらも証明できないのと同じ事であろうか。
　まるで､気の遠くなる様な難題で､数学者が笑わないのも､難題の前で笑えないのも､当然ではある。
　

P問題とNP問題

　時代が進み､分類が進化すると､NP問題の様な難題でもより効率的な解決策が見い出され､P問題の様に簡単に解けてしまう事もある。
　例えば､ある自然数が素数かどうかを判定する問題は､1970年代半ばからNP問題に属するとされていた。
　だが2002年､インド工科大の3人のコンピューター科学者が､無条件下での証明と巧妙なアルゴリズムを考案し､この問題がP問題に属する事をついに確認した。
　例えば､暗号化システムはその殆どがNP問題に基づく為､解読されてしまうかもしれない。また､生物学における50年来の課題であるタンパク質の折り畳みもより扱い易くなり､新たな治療薬の設計や産業廃棄物を分解する酵素の発見が促されるだろう。
　その他､日常的な難問の最適解を見出せる様になる日も近いとしたら・・・
　以下､｢50年越しの未解決問題に挑む
コンピューター科学者たち｣から一部抜粋です。

　｢P対NP問題｣は50年前､数理論理学と電子計算技術の融合という極めて重大な出来事以来､世界中の研究者がその解決の為に壮大な試みに挑んできた。
　コンピューター科学者の中には､その努力を(ギリシャ神話の)シーシュポスの苦行に喩える人もいる。
　だが､この問題を最初に探求し始めた研究者たちが解決策を見い出せないまま時間切れになる一方で､新しい世代は喜んで取り組んでいる。
　カリフォルニア大学のコンピューター科学者M･セービンは､｢P対NP問題｣の魅力は”太陽が地球を飲み込むまで答えが分からない”くらい困難な問題の不可能性を探る点にあると言う。しかし､”この問題に取り組まなければ後悔するだろう”とも語る。

　一方で､MITのコンピューター科学者マイケル･シプサ教授は､この問題に10年と(解決できる方に)30gの金を費やした。
　しかしそのお陰で､1980年代には”制限付き”モデルでこの問題の一部を解くという目覚ましい結果を提示する。やがて､｢P対NP問題｣は脚光を浴び､いくつかの成果も得られ､”解決はそう遠くない”という期待が持たれた。

それでも数学者は諦めない

　シプサ教授はP対NP問題をわかりやすく説明する為､基本的な掛け算の問題”7×13”から始めた。
　答えは91と簡単だが､これ以上大きな数になると多少難しくなるが､コンピューターを使えば一瞬である。
　だが､見方を変えると別の問題が発生する。例えば､97桁の素数を2つ掛け合わせると以下の様な莫大な数字になる。
　310 7418240490 0437213507 5003588856 7930037346 0228427275 4572016194 8823206440 5180815045 5634682967 1723286782 4379162728 3803341547 1073108501 9195485290 0733772482 2783525742 3864540146 9173660247 7652346609
　この素因数分解問題は､暗号に用いられるRSA鍵の解読の難易度を理解する課題の一部だ。事実､この問題を解くのに80台のプロセッサーで5カ月間計算し続けたが､1台では約33年かかる計算だ。
　素因数分解が難しいのは､天文学的な数の可能性を1つずつ確認する”力づくの方法”しかないからだ。ただコンピューターといえど､これでは時間が掛かりすぎる。

　ここで興味深いのは､”本当に検索する必要があるのか？という事だ”と教授はいう。　
　”或いは検証せずに素早く素因数分解の解を見つけられる様な解法があるのか？それはまだわかりません”
　これこそが”計算複雑性”の核心に触れる問題であり､計算複雑性の分野には取り組むべき数多くの難解な問題で溢れている。
　P問題は”全ての始まりのクラス”であり､数学的に言えば､解を求める時間がn²の様な多項式関数で記述できる問題をP問題と呼ぶ。
　この多項式時間アルゴリズムでは､nは入力のサイズであり､その入力に対して解を求めるのに掛かる時間は､合理的な割合(この場合はn²)で成長する。
　一方で困難なNP問題の中には､実行時間が2ⁿの様な指数関数(の様に急激な増加)で定義されるアルゴリズムでなければ解けないものがある。

　因みに､(計算量理論における)Pとは多項式時間(polynomial time)で解ける判定問題の集合であり､(計算複雑性理論における)NP(Non-deterministic polynomial time)とは複雑性クラスの1つであり､答えがYesとなる様な問いに対し､非決定性(Non-deterministic)多項式時間で検証できる問題のクラスである(ウィキ)。

　アーロンソン教授曰く。
　｢NP問題｣は”破れた希望と空しい夢のクラス”だと言う。しかしながら､”あらゆるNP問題が難しい訳ではない”とも語る。
　実際､クラスNPはクラスPを含む。
　それは､簡単に解ける問題は(当然ながら)検証も簡単だからだ。
　(冒頭でも言った様に)難易度の高いNP問題は､極めて重要な実用性がある事が多い。
　こういった問題を解く際に､力づくで探索する方法をとると､解を得るに非現実的な長い時間(数億年単位)が掛かる可能性がある。
　つまり､”力まかせ”の探索アルゴリズムが最良のアルゴリズムならば､明らかにクラスPとクラスNPは等しくない事になる。
　そしてそれは､往々にして我ら人類に不幸な結果をもたらす。
　以上､MIT Techからでした。

最後に〜｢NP問題｣とウクライナ危機

　今プーチンがやってる事は､この”力任せ”の侵攻に過ぎない。
　この狂ったバカに｢NP問題｣を解かせたら､延々とコンピュータの前に居座り､”俺にはスパコンがある”と(ふんぞり返り)エンタキーを押し続けながら､数億年の時をたった独りで過ごすつもりなのだろうか。

　全ての問題や行為や､それらがもたらす結果には､緻密な検証が必要である。
　この｢NP問題｣が”破れた希望と空しい夢のクラス”ならば､プーチンのウクライナ侵攻は”破れた野心と虚しい野望”に終わる破壊工作となる。
　どんなに簡単な事でも力ずくで行おうとすると､やがては取り返しのつかない難しい問題に沈下する。
　それこそが､(容易な筈だった)P問題が(難解な)NP問題になりうる時かもしれない。

　しかし､P問題を数学的アルゴリスムを使って検証すれば､簡単に答えが引き出せる様に､今のウクライナ危機もプーチンの狂った野望として検証すれば､答えは意外と単純かもしれない。
　いや､解決には(｢NP問題｣と同様に)延々と長引くかもしれない。

　領土的野心というプーチンの単純な強欲が､ウクライナ侵攻に繋がり､やがて戦争から大量破壊に変質する。そして最悪､複雑で解決の見通しが全くきかない難題として､延々と燻り続ける。
　つまり､単純な筈のP問題が､解決困難なNP問題に発展する。
　まさに､”P問題⊂NP問題”という｢NP問題｣の構図がそのまま､今回のウクライナ危機の最悪のシナリオとなってしまう。

　ウクライナ危機を上手く検証し､最悪の結末を回避する数学的アルゴリズムは､果たして存在するのだろうか？
　それとも､プーチンの狂気を沈めるアルゴリズムが存在するのだろうか？