ミニ研究集会（Complexity）の報告

上原先生のお誘いにより，今回初めてＬＡの会誌に寄稿させて頂くことになりました． 特定領域研究「新世代の計算限界」のcomplexityに関するミニ研究集会に参加・講演しましたので，拙筆ながらその参加報告を書きたいと思います．

本ミニ研究集会は，電通大の垂井先生によりcomplexityに非常に広い意味で関連がある話，最近の展開のサーベイやオープンプロブレムに重点を置いた話，オープンプロブレムというよりはオープンプロジェクトとでも呼ぶべき「こんなことができるといいな」という部分を含む話を歓迎する，という意向のもとに企画されました．詳しい情報に関しては以下の通りです．各講演の内容は私が聴講した内容と予め配布された講演者の方々が書かれた概要をもとに書いてます．

開催日時:

2005年10月11日（火）9:30 -- 17:30

開催場所:

東京工業大学大岡山キャンパス西8号館(W)8階809号室

定兼 邦彦（九大），索引を用いた文字列検索の計算量と未解決問題

文字列中のパターンの検索を行う場合，予め索引を作成しておくことにより高速化が可能となるのですが，索引のサイズと検索時間の間にはトレードオフが存在します．この講演では，様々な索引の構成方法と検索時間との関係の解説があり，その検索時間の下界に関する予想をお話されていました．

河内 亮周（東工大），オラクル同定問題に対する量子質問計算量の幾何学的な特徴付け

オラクル同定問題とは与えられたブラックボックスブール関数（オラクル）に質問を行い，候補関数集合の中のどれがオラクルとして与えられているかを同定する問題です．この講演では幾何学的な観点から二つの関数の間に内積を定義し，その内積により重要な例題を含む特殊なオラクル同定問題の量子質問計算量の上界の特徴付けが述べられ，その一般化に関する説明が行われました．

来嶋 秀治（東大），閉ジャクソンネットワークの正規化定数の近似計算法について

閉ジャクソンネットワークの積形式解の正規化定数はスループットなどの様々な情報を与えてくれることが知られています．この講演では，閉ジャクソンネットワークの積形式解の正規化定数の計算に対してFPRASを与えるマルコフ連鎖モンテカルロ法による近似アルゴリズムの設計，更に近似解の精度保証についてお話されていました．

山本 真基（東工大），MAX2SAT の Average Case 時間計算量について

これまでにSATに関する平均ケースの計算量の研究はなされていますが，MAXSATに関しては全くなされていません．この講演ではMAX2SATのある良い性質を満たす例題集合（例題集合全体がNP-hardとなり，各例題の節の数が高い確率で比較的小さい）に対して平均ケースで高速なアルゴリズム設計についての考察が述べられました．特にこの例題集合のほとんどの場合が局所探索型アルゴリズムにより高速に解けることの予想とその直観について議論がなされました．

渡辺 治（東工大），確率伝播法とその発展形について

前の講演の内容と連携した平均ケースに関する高速アルゴリズムの設計について，確率伝播法と呼ばれる新しい手法に基づいた講演でした．確率伝播法は統計情報処理の強力な手法として統計力学の研究者により再発見され，現在非常に盛んに研究されています．この講演では SAT 及び関連する問題について確率伝播法の適用可能性についてお話されていました．

森住 大樹（京大），否定数を log (n+1)に限定した回路計算量の下界について

否定数を[log (n+1)] ([]は小数切捨て記号です;上原注)に限定した回路においてΩ(n log(n))の下界を示すことができれば，一般の回路における同等の下界を示したことになることが知られており，否定数限定回路は回路計算量において重要であることが知られています． この講演では，否定数をlog(n+1)に限定した回路に対してn入力2出力論理関数 (PARITY, ¬PARITY) の回路計算量の下界5n-cの証明についてお話され， その下界の更なる改良について議論されていました．

天野一幸（東北大），単調DNF式のいくつかの性質

この講演では，単調DNF式の充足割当の個数を最大化あるいは最小化するような式の性質についていくつかの実験的事実が説明され，その性質を証明するためのアプローチについての議論が行われました．またLaplante--Lee--Szegedy [LLS05]らによる量子計算における質問計算量の下界証明テクニックを古典計算の formula complexity の下界証明へ応用について，その下界の更なる改良について考察が述べられました．

垂井 淳（電通大），k-wise independent permutations

N置換の集合Pが任意のk個の点x₁,...,x_kに関してπをPから一様ランダムに選んだ場合，π(x₁),...,π(x_k)の分布がランダム置換のものと（ほとんど）一致するときPは k-wise (almost) independent であると言います．この講演では，kが大きいときでもそのようなPがFeistel変換による合成により生成する方法が説明されました．また Reingold によるUSTCONN∈LOGSPACE[Rei05]のReingold--Trevisan--Vadhan[RTV05]の拡張がこの問題に適用できるという Kaplan--Naor--Reingold[KNR05]の指摘についても解説され，関連する未解決問題についても触れられていました．

垂井 淳（電通大），NP≠coNPを証明するには？

この講演は NP≠coNP という仮定が正しいとして，この証明がどのような証明法では見込みがないかについての研究の提案でした．以下のような現時点での方針を説明されていました．(共同研究者募集中とのことです．) 3SATの式Fが充足不可能かつZFでの充足不可能性証明が長い事をLong(F)とすると，NP≠coNPならばLongなFが存在する．従って，明示的なFに対してLong(F)であることを短いサイズの証明で示すことは出来ない．同時に多項式個の式F₁,...,F_pに対してF₁∨…∨F_pがLongであることも短いサイズの証明で示すことは出来ない．更に3SATの式の巧い確率的生成を与え，生成される式が確率1/poly(n)でLongになるという証明法に対しても，もしそのような証明が可能ならば多項式個のF₁,...,F_pに対してLong(F₁) or ... or Long(F_p)であることがcomplexity-theoretic assumptionのもとでのderandomizationにより証明できてしまうことになるのでそんなことはできそうにない．

参加した私の個人的な感想では，complexityという分野を前提に今回の研究集会は企画されたかと思うのですが，complexityとは直接的には関係しない多様な分野間に跨った土壌を元にcomplexityの理論が形成されているという実感が得られ，大変勉強になりました． 例えば，定兼先生の文字列検索の講演で紹介されたDemaine--López-Ortizの下界[DL03]も私の講演が対象にしている質問計算量的な観点からの結果ですし，私の質問計算量の話と天野先生の講演で紹介された[LLS05]に現れる量子計算の下界証明手法というのも実は本質的に量子情報理論で培われた議論を土台としています．結果だけに着目するとそれぞれあまり関連がないような話題なのですが，実はこのように掘り下げてみると手法や背景に数多くの共通点が見つけられ，これらの本質的な部分を垣間見ることが出来たのは大きな収穫でした．

また，昼食のときに垂井先生が私に「エキスパンダー同好会」を作ったらメンバー集まるかな？というお話をされていました．ご存知の方も多いと思いますが，エキスパンダーという特殊なグラフは近年盛んに研究されているcomplexityの重要なツールです．今回の研究集会の講演でも山本さんが対象とされていた良い性質を持つMAX2SATの例題集合はエキスパンダーを元に生成されたものですし，また昨年話題になったDinurによる組み合わせ論的なPCP定理の証明[Din05]もエキスパンダーをその基本としています．私自身もエキスパンダーには非常に興味があるのですが，まだまだ不勉強のため，同好会結成時には是非参加して鍛えたいと思っています:)

[Din05]

I. Dinur. The PCP theorem by gap amplification. ECCC TR05-046, 2005.

[DL03]

E. Demaine and A. López-Ortiz. A linear lower bound on index size for text retrieval. J. Algo., Vol. 48, No. 1, pages 2--15, 2003.

[LLS05]

S. Laplante, T. Lee, and M. Szegedy. The quantum adversary method and classical formula size lower bounds. In Proc. CCC '05, pages 76--90, 2005.

[KNR05]

E. Kaplan, M. Naor, and O. Reingold. Derandomized constructions of k-wise (almost) independent permutations. In Proc. APPROX-RANDOM '05, pages 354--365, 2005.

[Rei05]

O. Reingold. Undirected ST-connectivity in log-space. In Proc. STOC '05, pages 376--385, 2005.

[RTV05]

O. Reingold, L. Trevisan, and S. Vadhan. Pseudorandom walks in biregular graphs and the RL vs. L problem. ECCC TR05-22, 2005.

Back to Table of Contents Last modified: Thu Jul 21 08:14:25 JST 2005 modified/maintained by R.Uehara (uehara@jaist.ac.jp)