・とある理由により、近所の消防団に予備団員として加入することになった。救命講習を受けたり誘導訓練などを行うらしい。世界の半分は燃えている。炎を前にして人は率直であらずにはいられない。
・今月、絶対に外せないノルマとして設定されていた仕事をようやく終えることが出来た。クリティカルなバグの看過を免れたどうかは、人知の及ばぬ神のみぞ知るところだが、それでも人事を尽くすことで、その蓋然性をかなりのところまで高めることが出来たのではないかと感じる。それにしても、シミュレーション環境を構築した先輩の強まり具合が半端ない。あやかりたいものだ。
あと残された24時間で自分個人のタスクを完了すれば10月は少し身軽に過ごせそうだ。(とはいっても、かなり無理目な量なので、すでに敗色は濃厚か。人に迷惑はかからないので甘んじて受けいれよう。)
・ということで心機一転、秋からは半端にしていた勉強などを再開したいと考えている。具体的にターゲットを絞ったほうがいいだろう、ということでP=NP問題の周辺を探ってみることにした。
P≠NP
かいつまんで言葉にしてみる。まずP問題とは実際的な時間で計算できる問題であるとする。それに対してNP問題は「少なくともしらみつぶし的な方法では解決できて、またひとたび解答の候補が得られれば、それが正しいものであるか否かは実際的計算時間において判定できる」といった問題である。このクラスに属する問題で、NPであってもPではない問題というものが存在するのかどうか。これがP=NP(P≠NP)問題だ。また、現在のところNP問題であると認識されているもののうちで、応用的にも意義深い多種多様な問題がNP完全と呼ばれるクラスに属していることが知られている。すべてのNP問題は、NP完全問題である命題論理の充足可能性問題に帰着させることができるという著しい特徴を持つ。すなわち、あるひとつのNP完全問題がPであるならば、自動的にP=NPという結論が得られるのである。
例えば公開暗号鍵体系において暗号化鍵から復号化鍵を導くという逆演算、あるいはVLSIの設計において有用性の認められるある種のグラフ問題などが、このNP完全に属していることが確認されている。そして、これらのうちでひとつでもPに属する、あるいは属さないことが確認されると、先述した性質によりNP完全に属するすべての問題において同等の結果が得られるということになる。もしこの問題が肯定的にせよ、否定的にせよ解決されたならば、現実的にも大きなインパクトを与えることになるのは間違いない。
難問中の難問として君臨するこの問題に挑みかかりたいなどとは、自分に言えたものではないけれど、数理論理学や有限数学など、関連する分野の勉強をしながら最新の結果を覗いてみることくらいは、望んでみてもバチはあたらないだろう。とはいえ、このおぼつかない脚力では、数々の優れた数学者が特攻していった奈落の淵に辿り着けるかどうかすら、非常に怪しいものなのだが。特に興味あるのはサーキット計算量の話(これはちょっと仕事に関係ある)と、コーエンの強制法との関係について。
・今月、絶対に外せないノルマとして設定されていた仕事をようやく終えることが出来た。クリティカルなバグの看過を免れたどうかは、人知の及ばぬ神のみぞ知るところだが、それでも人事を尽くすことで、その蓋然性をかなりのところまで高めることが出来たのではないかと感じる。それにしても、シミュレーション環境を構築した先輩の強まり具合が半端ない。あやかりたいものだ。
あと残された24時間で自分個人のタスクを完了すれば10月は少し身軽に過ごせそうだ。(とはいっても、かなり無理目な量なので、すでに敗色は濃厚か。人に迷惑はかからないので甘んじて受けいれよう。)
・ということで心機一転、秋からは半端にしていた勉強などを再開したいと考えている。具体的にターゲットを絞ったほうがいいだろう、ということでP=NP問題の周辺を探ってみることにした。
P≠NP
かいつまんで言葉にしてみる。まずP問題とは実際的な時間で計算できる問題であるとする。それに対してNP問題は「少なくともしらみつぶし的な方法では解決できて、またひとたび解答の候補が得られれば、それが正しいものであるか否かは実際的計算時間において判定できる」といった問題である。このクラスに属する問題で、NPであってもPではない問題というものが存在するのかどうか。これがP=NP(P≠NP)問題だ。また、現在のところNP問題であると認識されているもののうちで、応用的にも意義深い多種多様な問題がNP完全と呼ばれるクラスに属していることが知られている。すべてのNP問題は、NP完全問題である命題論理の充足可能性問題に帰着させることができるという著しい特徴を持つ。すなわち、あるひとつのNP完全問題がPであるならば、自動的にP=NPという結論が得られるのである。
例えば公開暗号鍵体系において暗号化鍵から復号化鍵を導くという逆演算、あるいはVLSIの設計において有用性の認められるある種のグラフ問題などが、このNP完全に属していることが確認されている。そして、これらのうちでひとつでもPに属する、あるいは属さないことが確認されると、先述した性質によりNP完全に属するすべての問題において同等の結果が得られるということになる。もしこの問題が肯定的にせよ、否定的にせよ解決されたならば、現実的にも大きなインパクトを与えることになるのは間違いない。
難問中の難問として君臨するこの問題に挑みかかりたいなどとは、自分に言えたものではないけれど、数理論理学や有限数学など、関連する分野の勉強をしながら最新の結果を覗いてみることくらいは、望んでみてもバチはあたらないだろう。とはいえ、このおぼつかない脚力では、数々の優れた数学者が特攻していった奈落の淵に辿り着けるかどうかすら、非常に怪しいものなのだが。特に興味あるのはサーキット計算量の話(これはちょっと仕事に関係ある)と、コーエンの強制法との関係について。