Blog
吉田です。最近ACM Symposium on Theory of Computing (STOC)という学会に投稿していた論文が受理されました。論文はECCCにアップロードしています。STOCは次回が43回目の開催となる理論計算機科学(要するにアルゴリズムと計算量を扱う分野)の中では最高峰の学会です。例えばCookが初めてNP完全性という概念を提唱したのもSTOCです。
今年は4年に一度のFederated Computing Research Conference (FCRC)というイベントがあり、STOCの他にもEC (ゲーム理論、オークションなど), CCC (計算量)、PODC, SPAA (共に分散/並列アルゴリズム)など18個の学会が同時開催されます。逆に言うと18個のうちのどれかに論文が受理されれば全体に参加出来るお得なイベントで(勿論お金さえ出せば参加は可能ですが)、僕もどれかに当たれば良いなぐらいの気分でした。
折角ですので、今回はSTOCに通った論文の内容を簡単に紹介したいと思います。流石に細部まで話をするのは技術的になりすぎてしまうので、雰囲気だけ感じ取ってもらえれば十分です。もう少し詳しい所まで踏み込んだスライドを最後に添付しておきますので、興味のある方は読んでみてください。’
タイトルは以下の通りです。
邦題: 次数制限モデルにおける全てのCSPに対する最適な定数時間近似アルゴリズムと近似困難性
タイトルが全てを語っているのですが予備知識が無いと意味が分からないと思います。なのでまずそこから説明しましょう。
まずCSP (Constraint Satisfaction Problem, 制約充足問題)とは、変数の集合\(V\)と、変数に対する制約\(\mathcal{P}\)の組からなるインスタンス\(I=(V,\mathcal{P})\)が与えられ、全ての制約を満たすように変数に値を入れることが出来るかという問題です。
例えば、
変数集合\(V = \{x,y,z\}, x,y,z \in \{0,1\}\),
制約集合\(\mathcal{P} = \{(x \vee y), (y + z = 1 \pmod{2}), (x \wedge z)\}\)
からなるインスタンス\(I=(V,\mathcal{P})\)は、CSPのインスタンスの一例です。この時\((x,y,z) = (1,0,1)\)とすれば、全ての制約を満たすことが出来ます。使う制約に応じて、CSPはSATと呼ばれたり、Horn SATと呼ばれたり、グラフの二彩色性/三彩色性と呼ばれたり、線形連立方程式と呼ばれたりします。もっと馴染みのある例では数独もCSPの一例です。
これだけ多くの問題を一般化しているCSPは、理論計算機科学の分野でも重要と思われていて、研究もかなり数が多いです。但し一般にCSPはNP完全なので充足可能性判定という意味では余りやれることは多くありません。そこで全ての制約を満たす代わりに、出来るだけ多くの制約を満たすという最適化問題もよく考えられています。これをMax CSPと呼び、Max CSPも使う制約に応じてMax SAT, Max Horn SAT, Max Cutなどと呼ばれたりします。
Max CSPはCSPを含むのでNP困難ですが、CSPと違って近似を考えることが出来ます。インスタンス\(I\)に対して、最も多くの制約を満たすことが出来る変数への値の割り当てを\(x^{*}(I)\)と書き、その時に満たされる制約の個数を\(\mathrm{opt}(I)\)と書くことにしましょう。そうしたときに、\(\alpha \cdot \mathrm{opt}(I)\)個の制約を満たすことが出来る割り当て\(x\)を\(I\)に対する\(\alpha\)近似解と呼びます。また\(\alpha\)近似アルゴリズムとは、任意のインスタンス\(I\)に対して\(\alpha\)近似解を出力することが出来るアルゴリズムのことを言います。\(\alpha\)は\(1\)に近ければ近いほど良いです。目標は出来るだけ大きい\(\alpha\)に対して、多項式時間\(\alpha\)近似アルゴリズムを作ることです。
この分野は非常に良く研究されていて、特に半正定値計画法(Semidefinite Programming, SDP)という線形計画法(Linear Programming, LP)を拡張した手法がよく使われています。例えばMax Cutという問題がSDPの典型的な応用例です。Max Cutはグラフが与えられ、頂点集合を二つに分けて、その間に跨る枝の本数を最大化するという問題なのですが、Max CSPとしても表現することが出来ます。これに対してSDPを用いると\(\alpha_{\textrm{MC}}=0.878\cdots\)という近似度が得られることが知られています。
では各CSPに対して、多項式時間で得られる最大の近似度は何なのかということが気になってきます。例えばMax 3SATと呼ばれる問題では、(SDPを使わずに)近似度\(7/8\)が得られることが分かっており、また任意の\(\epsilon>0\)に対して近似度\(7/8+\epsilon\)を得るのはNP困難であることが知られています。
けれどもSDPを使ったアルゴリズムの近似度は一般的に無理数で、そのような近似度がタイトであるとは既存の手法からは言えそうにありませんでした。
この問題を解決するために提唱されたのがUnique Games Conjecture (UGC)です(Khot, STOC 2002)。UGCの詳細には立ち入りませんが、UGCを仮定すると、全てのCSPに対してSDPを超える近似解を得るのはNP困難であると示されました(Raghavendra, STOC 2008)。つまり先ほどのMax Cutの例でいうと任意の\(\epsilon>0\)に対して、\(\alpha_{\textrm{MC}}+\epsilon\)の近似解を得るのはNP困難であるということです。
よってMax CSPの近似に関する研究は、UGCが正しいかどうかという問題を除いて一定の決着を見たということになります。他にも、各CSPに対して具体的な近似度がいくらか計算するであるとか、計算量を多項式時間の中で下げる、と言った問題は残っていますが、上記の結果に比べれば細々していると言えるかもしれません。
さて今回私が研究したのはMax CSPの定数時間近似です。定数時間近似は2005年頃から流行りだしたトピックで、その名のごとく”定数時間”で近似します。ここでいう定数時間とは入力サイズに依らないという意味で、Max CSPの文脈では変数の数や制約の数に依らないという意味になります。入力を全部読むことは出来ませんが、そこは入力にアクセスするオラクルが有ると仮定していて、今回のモデルでは
- 変数を一つランダムに取り出す
- 指定した変数を使っている制約を一つ取り出す
ということが出来るとします。ただこれだけでは、先ほどの近似の定義のもとで近似をするのは不可能なことが簡単に示せるので、\((\alpha,\epsilon)\)近似というものを導入します。制約を\(m\)個持つインスタンス\(I\)に対して、\(\alpha \cdot \mathrm{opt}(I) – \epsilon m\)個の制約を満たすことが出来る解\(x\)を\(I\)に対する\((\alpha,\epsilon)\)近似解と言います。\(\alpha\)近似と違うのは\(\epsilon m\)という加法的なエラーを許していることです。\((\alpha,\epsilon)\)近似アルゴリズムとは、任意のインスタンス\(I\)に対して\((\alpha,\epsilon)\)近似解を確率\(2/3\)以上で出力することが出来るアルゴリズムのことを言います。さらに今回のモデルでは変数の次数(変数が現れる制約の個数)が定数であると仮定しています。
一見すると各変数に値をランダムに入れてみて、満たされた制約の個数を近似して返すぐらいのことしか出来なさそうです。それに対して今回の論文では実はLPを使った近似を定数時間で行うことが出来るよと示し、さらにそのLPで得られる近似度を超えるのは定数時間では無理だよと示しました。つまり先ほどのRaghavendraの結果を定数時間近似の世界に自然に拡張したということになります。
例えばMax Cutの場合は、多項式時間での近似を考えると、SDPでは\(\alpha_{\mathrm{MC}} = 0.878\cdots \)という近似度が得られ、LPでは\(0.5\)しか得られないことが分かっています。なので今回の論文の結果を用いると、定数時間で\(0.5\)という近似度は得ることが出来るけれども、任意の\(\epsilon>0\)に対して\(0.5+\epsilon\)という近似度を定数時間で得ることは出来ないということがすぐに示せます。
今回の結果は示唆に富んでいて、例えばSDPを計算するにはインスタンス全体の情報が無いといけないが、LPを解くには実はローカルな情報だけで良いということを言っています。こういうことは感覚的にはそんな気がすると思っていたわけですが、それを実際に定量的に示せたのは面白いことだと思います。
最後にもう少し詳細に踏み込んだスライドを添付しておきます。興味があれば見てみてください。
Tag
