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


   日時  ：１０月２８日（火） １５：３０〜１７：３０
   場所  ：電気通信大学 西９号館 ３階（または５階）
   連絡先：0424-83-2161 ext.3288
           電気通信大学 情報工学科 山崎 浩一 （西９号館 ５階 ５０４号室）
	   e-mail:yamazaki@cs.uec.ac.jp

  題目：グラフの到達可能性判定問題の領域計算量について
　発表：戸田誠之助（日本大学文理学部応用数学科）
　概要：

　　今回は，グラフの到達可能性判定問題の領域計算量について議論する．
　この問題はとても古いものではあるものの，領域計算量の理論における
　基本的な問題であり，近年Nisanとその周辺のグループによって盛んに
　研究が進めらている．これまでのNisanらの研究によって，この問題が
　決定性log^{4/3}(n)領域で判定可能であることが知られているが，決
　定性対数領域で計算できるかどうかはまだ十分な予測ができない状況に
　ある．一方，この問題が決定性対数領域で判定できるようなグラフの
　適当な部分クラスを発見することも興味ある課題であると思うが，現時
　点では木全体からなるクラス以外については全くなにも分かっていない．

　そこで，到達可能性判定問題が決定性対数領域で判定できるような非自明
　なグラフのクラスを発見することを目的とした発表者の分析結果を述べた
　あとで，参加者に対して幾つかの問題提起をしたい．

　興味を持った皆さんは私と一緒に考えて下さい．