特定領域研究「新世代の計算限界」関係者のみなさま cc: comp研・SIGAL・complexity seminar メーリングリスト上のみなさま complexityに関する研究集会を以下のように開催します。 垂井淳 電気通信大学情報通信工学科 tarui@ice.uec.ac.jp 以下：　１．プログラム　２．会場への行き方　３．アブストラクトのリスト　です。 -------------------- 日時：　１０月１１日（火）　９：００−−１７：４５ 場所：　東工大大岡山キャンパス西８号館 (W) ８階８０９号室 発表機材：　パソコンプロジェクター、OHP、ホワイトボード ９：００-９：３０：　山本真基　東工大 MAX2SAT の Average Case 時間計算量について ９：３０-１０：１５：　河内 亮周　東工大 オラクル同定問題に対する量子質問計算量の幾何的な特徴付け １０：１５-１０：３０　休憩 １０：３０-１１：１５：　来嶋 秀治　　東大 閉ジャクソンネットワークの正規化定数の近似計算法について １１：１５-１２：００：　築地立家　東京電機大 ＡＮＤを計算する３段ＭＯＤ回路の下界 １２：００-１３：３０　休憩 １３：３０-１４：１５：　定兼邦彦　九大 索引を用いた文字列検索の計算量と未解決問題 １４：１５-１５：００：　森住 大樹　京大 否定数をlog(n+1)に限定した回路計算量の下界について １５：００-１５：１５　休憩 １５：１５-１６：００：　渡辺治　東工大 確率伝搬法とその発展形の可能性について １６：００-１６：４５：　垂井淳　電通大：　 NP neq coNPを証明するには？（ショートトーク） k-wise almost independent permutations １６：４５-１７：００　休憩 １７：００-１７：４５：　天野一幸　東北大 （タイトル未定） ------------------------------------------------ 東工大西８号館 (W) ８０９号室への行き方 大岡山駅を出て左を見れば正門が見えます．我々の建物は西８号 館(E)です．西８号館(E) は新しく立った建物です．本館西側にた っています．本館に向かってあるき，向かって右の新しいビルを 目指して，スロープを下れば入口です．入ったところが (E) 棟３階 です．そのフロアをまっすぐ進むと (W) 棟に入ります．そこのエレ ベータを使って８階に来て下さい．エレベータを出て，まっすぐ進 んだつき当たりが８０９号室です． ------------------------------------------------- アブストラクト 山本真基　東工大 MAX2SAT の Average Case 時間計算量について これまでに，MAXSAT および MAX-k-SAT に関する Average-Case 時間計算量の研究は，（筆者の知る限り）全くされていない． （SAT に関してはある．） 本講演では，MAX2SAT 問題を考え，以下のような性質を持つ 例題生成器 RGEN が生成する例題族 F(RGEN)に対して， Average-Case 時間計算量を議論する． 1. RGEN が出力する例題と真理値割り当ての対のほとんど（任意の コンスタントの割合 1-ε）が，例題とその最大充足解の対である． 2. RGEN の生成する例題の大きさは小さい．つまり，2CNF 論理式 の節の数が，変数の数の（εに関する）コンスタント倍である． 3. RGEN が出力する全例題上の MAX2SAT 問題が NP-Hard である． F(RGEN) のほどんど（all but o(1)）が，Local Search タイプの アルゴリズムに弱いことの直感的説明をし，それを示すための 方法について議論する． -------------------- 河内 亮周　　東工大 オラクル同定問題に対する量子質問計算量の幾何的な特徴付け オラクル同定問題とは与えられたブラックボックス関数（オラクル）に質問を行 い，候補関数集合の中のどれがオラクルとして与えられているかを同定する問題 である．本講演では候補関数集合の幾何的な特徴に着目して同定に必要な量子質 問計算量について議論する． -------------------- 来嶋 秀治　　東大 閉ジャクソンネットワークの正規化定数の近似計算法について 閉ジャクソンネットワークの積形式解の正規化定数に対する近似計算法を提案する。 提案するアルゴリズムはマルコフ連鎖モンテカルロ法で、FPRASを与える。 本発表では特にモンテカルロ法に焦点をあて、近似解の精度保証について議論する。 -------------------- 定兼邦彦　九大 索引を用いた文字列検索の計算量と未解決問題 文字列中のパタンの検索を高速化するために、あらかじめ索引を付加する手法が とられているが、索引のサイズと検索時間の間にはトレードオフが存在する。本発表では 既存の索引について解説し、検索時間の下限に対する予想を立てる。 -------------------- 森住 大樹　京大 否定数をlog(n+1)に限定した回路計算量の下界について 否定数をlog(n+1)に限定した回路における n入力2出力論理関数(PARITY, $€neg$PARITY)（ただし，n+1は2の累乗）の 回路計算量の5n-cの下界の証明について紹介し， そこからの発展の可能性に触れる． 否定数を$€lceil €log(n+1) €rceil$に限定した回路において $€omega(n€log(n))$の下界を示すことができれば，一般の回路における 同等の下界を示したことになることが知られており， 否定数をその数に限定した回路の回路計算量を 調べることは特別な意味を持つ． -------------------- 渡辺治　東工大 確率伝搬法とその発展形の可能性について 統計力学の研究者により再発見され，非常に盛んに研究されて いる確率伝搬法について，それがどの程度まで有効（そう）な のか，他の局所探索法と比べて，どのように違うのか／同じな のか，を，たとえば SAT 問題（とその variation）に絞り，議論 してみたい． -------------------- 垂井　淳　　電通大 NP neq coNPを証明するには？（ショートトーク） （この話についての現時点でのアイデア・中身はおおむね以下のみ；共同研究者募集中） NP neq coNPであるという前提のもとに、このことの証明がどのような方法では無理そうか ということを考えたい。3SATフォーミュラFについて、それが充足不可能であって、かつ、 （普通の数学を展開する公理系としての）ZFでの充足不可能性の最短証明が長いことを Long(F)と表すことにする。NP neq coNPであればLong なFが存在する。 （１)あるexplicitなFに対してLong(F)であることを、（我々にとって自然である）コンスタントまたは 短いサイズの証明で示すことはできない。そのような証明がないことがLong(F)の主張だから。 （２）２つのexplicitなフォーミュラF1,F2に対して「Long(F1)orLong(F2)」のコンパクトな証明がないことも 簡単にわかり、少し注意して拡張すればp=poly(n)個に対しても同様に「Long(F1)or...orLong(Fp)」の コンパクトな証明がないことがわかる。 （３）フォーミュラのうまい確率的生成を定義し、生成されるフォーミュラが確率1/poly(n)で Longになるという証明法に対しても、complexity-theoretic assumptionのもとでの derandomizationにより、もしそんな証明ができれば多項式個のF1,...,Fpに対して Long(F1)or...orLong(Fp)であることが証明できてしまうことになり矛盾するので そんなことはできそうにない、という議論を考えたい。 以上において充足不可能な3SATフォーミュラの代わりに、たとえば、「root(n)のクリークを 持たないn頂点グラフ」を用いても全く同じ議論となる。 -------------------- 垂井　淳　　電通大 k-wise almost independent permutations N置換の集合Pは次の性質を持つときk-wise (almost) independentであるという： 任意のk点x1,...,xkに関してpiをPから一様ランダムに選んだときのpi(x1),...,pi(xk)の分布が 完全にランダムな置換のもとでの分布と一致する・ほとんど一致する。このようなPを kが大きいときもFeistel変換のcompositionによる構成で生成することができることを示す。 Reingold によるブレークスルー：USTCONN in LogSpace[STOC05]の Reingold-Trevisan-Vadhan[ECCC05]による拡張が以上の問題に応用できるという Kaplan-Naor-Reingold[RANDOM05]の指摘、すなわち、もとのグラフのexpansion factorを 維持したzig-zag productによるpseudorandom walkの方法の応用についても簡単に説明し、 また、以上の問題に関連する未解決問題のリストを提示する。 以上