2007年01月22日計算機数理科学専攻・情報数理基礎論講座
安本研究室（安本雅洋教授）

有限と無限の境目、これが研究の中心テーマです。

数学では無限なものを主として取り扱うのに対して、計算機では有限なものを扱います。有限の中でも巨大な有限は無限と同じように扱われる、ということはよくあることです。巨大な有限とは何か？具体的にいうと、1000は巨大ではありませんが、10の1000乗は巨大だといっていいでしょう。もちろん巨大であるという概念に対して、厳密な定義ができるわけではありません。にもかかわらず我々は巨大という直感的な感覚を持っています。例えば、ある種の計算を繰り返す場合に1000回繰り返すことはできるでしょうが、10の1000乗回繰り返すなどということは、どんなに性能の良いコンピューターでも実際には不可能なことです。このことを利用したものの一つに、公開鍵暗号があります。公開鍵暗号は解読可能な暗号ですが、その解読には巨大な時間を要するであろう信じられている（証明されているわけではない）ので一応安全な暗号だとされているのです。

巨大な有限とは対照的に、無限の中に小さな無限とでもいえるようなものがあります。正確にいうと、実体は無限であるにもかかわらず形式的には（一階述語論理の範囲内では）有限と全く同じように扱えるもので「star有限」と呼ばれています。star有限の中では大きなstar有限と小さなstar有限との区別を定義することができ、巨大有限を大きなstar有限として解釈することによって、直感的な概念であった巨大有限を数学の研究対象にすることが可能になります。有限の世界では個々の存在がそれぞれきわめて個性的であり、従ってその取り扱いには泥臭くて面倒な計算が伴うのに対して、無限の世界では特定の存在を除くと大部分は没個性的であり、それゆえ統一的で美しい理論が作れるといった面があります。star有限はこれら二つの性質が混然として不思議な世界を作りだしています。計算量理論の基本的な未解決問題にＰ＝ＮＰ問題というものがあります。この問題は公開鍵暗号の安全性証明とも関係していてその重要性は広く認められているにもかかわらず、解明の糸口が全くないためほとんど誰も直接には研究していません。star有限の理論がこの問題の解決に役立つのではないかと考えここ数年取り組んできましたが、やればやる程この問題がなぜ難しいのかという理由だけがますますよくわかるようになってきたというのが現状です。

研究室の院生は上記の他、様相論理、Bounded arithmtic、計算量理論など数学基礎論と数理論理学の様々な分野の研究に取り組んでいます。

• 
•