>>> Complexity Seminar のお知らせ <<<

皆様，大分，御無沙汰してしまいました．申し訳ありません．さて，来年の
ことですが，以下のようにセミナーを開きます．是非，ご参加下さい．

   日時：１月１４日（土），午後３時から４時
   場所：西８号館 (W) 10 F コラボレーション・ルーム

   題目：有限置換群におけるグラフ自己同形問題の一般化について
   講演者：宮崎琢成 (Trinity College)

概要

周知のように，グラフ同型問題(GI)は計算量理論において長年にわたり研究され
ているが，その本質はほとんど知られていない．グラフ自己同形問題(GA)は，任
意のグラフが単位以外の自己同形を持つか否かを判定する，GIに似た問題であ
る．GAもGIと同様に，P叉はNP完全に属するか分かっていない．GIに関する重要
な未解決問題の一つは，GAの計算量とGIのそれの差を把握することである．

この未解決問題をより郡論的な観点から理解するため，GAとGIにそれぞれ密接な
関係がある有限置換群における共通郡問題(G-INT)と共通剰余類問題(C-INT)を考
える．実際，今のところ，GAとGIの関係はG-INTとC-INTのそれと同じに見える．
ここで今回は，G-INTとC-INTの間に位置する共通剰余郡問題(QG-INT)を定義し，
QG-INTの計算量的な特性について話す．

以上

東工大西８号館 (W)  コラボレーション・ルームへの行き方

大岡山駅を出て左を見れば正門が見えます．我々の建物は西８号
館(E)です．西８号館(E) は新しく立った建物です．本館西側にた
っています．本館に向かってあるき，向かって右の新しいビルを
目指して，スロープを下れば入口です．入ったところが (E) 棟３階
です．そのフロアをまっすぐ進むと (W) 棟に入ります．そこのエレ
ベータを使って１０階に来て下さい．エレベータを出て，まっすぐ進
んだつき当たりがコラボレーションルームです．

以上