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

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

この勉強会では複数回に分けて、計算量に関わる問題、とくにP≠NP問題を数理論理学的にアプローチする試みについて紹介します。最初に計算量理論を簡単に紹介したのち、Bussによる「限定算術」の階層がそれとどのように関わるかを説明します。さらに、限定算術の階層を等式系の無矛盾性証明を用いて分離する試みについて、次の二つの論文を紹介することにより報告します。

• CONSISTENCY PROOF OF A FRAGMENT OF PV WITH SUBSTITUTION IN BOUNDED ARITHMETIC, Journal of Symbolic Logic 2018, arXiv preprint
• Separation of bounded arithmetic using a consistency statement, Preprint

Skypeでの中継も行います。希望される方は「問い合わせ」からSkype idを送ってください。

なお、次回以降の開催日については出席者と調整します。

料金

• 一般 1000円
• 学生 500円
• 高校生以下無料

数学デーin大阪

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

参加者は、3Fで行われている数学デーin大阪(19時から22時)に参加することができます。(参加は自由ですが、参加してくださるととても嬉しいです。)

主催

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

HP

Twitter

場所

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

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

https://goo.gl/maps/QVb8nkJyR9o