10 Nov
2018
10 Nov
'18
12:23 a.m.
皆様
名古屋大学の吉信康夫です．
以下の要領で名古屋ロジックセミナーを開催します．多数のご参加をお待ちしております．
日時：11月16日 (金) 15:30〜 場所：名古屋大学大学院情報学研究科棟 314室
講演者：黒田 覚 (群馬県立大学) タイトル：限定算術と強制法
アブストラクト：1990年代に竹内外史と安本雅洋によって導入された限定算術における強制法の理論を， 2種の限定算術を用いて再構成し，P=NP問題や命題論理証明サイズの問題とジェネリック拡大の間の 関係について論じる．また，ALOGTIMEやNLOGSPACEなど，多項式時間計算可能クラスの部分クラスに 対応するジェネリック拡大の構成についても論じる．