計算量への数理論理学的アプローチ

ある問題を解くために最低でもどのくらいの時間やメモリが必要か見積もることは、コンピューターを使って計算をする上でとても重要なことです。このような見積もりを与えるのが「計算複雑度」であり様々な尺度が提案されています。もっともよく知られているのが「多項式時間P」と「非決定的多項式時間NP」です。しかし、これら計算複雑度の間の関係を数学的に厳密に証明することは多くの場合難しく、現状では経験的な議論に頼っています。例えば、NPであるような問題を解くのはPであるような問題を解くよりもずっと難しいであろうと予想されていますが、現状ではP≠NPも証明されていません。この問題を解決することはミレニアム懸賞問題の一つで、現代数学のもっとも困難で重要な問題とみなされています。

この勉強会では複数回に分けて、計算量に関わる問題、とくにP≠NP問題を数理論理学的にアプローチする試みについて紹介します。今回はSamuel Bussが定義した限定算術の階層を導入し、それが計算量クラスとどのように関係しているかを解説します。

料金

• 一般 1000円
• 学生 500円
• 高校生以下無料
• Skype参加無料：Skypeグループへのリンクを前日の同報メッセージで送付します。受け取れるようにしておいてください。

数学デーin大阪

海老江数理科学勉強会は数学デーin大阪の併設イベントです。

参加者は、3Fで行われている数学デーin大阪(19時から22時)に参加することができます。(参加は自由ですが、参加してくださるととても嬉しいです。特に講師は参加しているので、講師や参加者と個人的に話したい方はご参加ください。)

主催

大阪分散技術コミュニティ(DTC)

HP

Twitter

場所

JR海老江駅、阪神電車野田阪神駅、地下鉄千日前線野田阪神駅、から徒歩5分

JR野田駅は最寄り駅ではないので注意。

https://goo.gl/maps/QVb8nkJyR9o