限定算術上の強制法の基礎

• Date/Time: June 22, 2012 (Friday) / 16:00 - 17:00

• Speaker: 高嶋 大翼 氏 (東北大学大学院 理学研究科)

• Venue: Rm 1201, Science Complex A, Tohoku Univ.

• Abstract: 限定算術と計算量クラスには対応関係があることが知られている． これにより，計算量クラスの分離問題を， 対応する公理の証明能力の違いのように考えることが出来る． 竹内外史と安本雅洋によって，１９９６年に， 限定算術上でブール値モデルを構成する論文が発表された． 本発表では，限定算術と計算量クラスの対応関係を確認し， 限定算術上でブール値モデルを構成する方法について概説する．