分離補題
解の数を減らす技術

理論計算機科学において、分離補題（isolation lemma、またはisolation lemma）とは、問題に対する解が存在する場合に、その解の数を1つに減らすランダム化アルゴリズムを指します。これは、解空間が空でない場合、無視できない確率で、これらの追加制約を満たす解が正確に1つだけ存在するようなランダム制約を構築することによって実現されます。分離補題は、計算複雑性理論におけるヴァリアント・ヴァジラニの定理や戸田の定理など、計算機科学において重要な応用があります。

最初の分離補題は Valiant と Vazirani (1986) によって導入されたが、その名前ではなかった。彼らの分離補題はランダムな数のランダム超平面を選択し、無視できない確率で、固定された空でない解空間と選択された超平面との交差にちょうど 1 つの要素が含まれるという性質を持つ。これはValiant–Vazirani の定理を示すのに十分である。つまり、ブール式の充足可能性問題から、ブール式が一意の解を持つかどうかを検出する問題への、ランダム化された多項式時間縮約が存在する。Mulmuley、Vazirani および Vazirani (1987) は、少し異なる種類の分離補題を導入した。ここでは、解空間のすべての座標に、一定範囲の整数でランダムな重みが割り当てられ、無視できない確率で、解空間に最小の重みを持つ要素がちょうど 1 つ存在するという性質を持つ。これを使用して、最大マッチング問題 に対するランダム化された並列アルゴリズムを取得できます。

文献では、様々な状況における様々なニーズに対応するために、より強力な分離補題が提案されてきました。例えば、Chari、Rohatgi、Srinivasan (1993) の分離補題は、Mulmuleyらの分離補題と同様の保証を備えていますが、使用するランダムビット数が少なくなっています。指数時間仮説の文脈において、Calabroら (2008) はk-CNF式の分離補題を証明しました。Noam Ta-Shma [1]は、やや強力なパラメータを持つ分離補題を提示し、重みドメインのサイズが変数の数よりも小さい場合でも、非自明な結果をもたらします。

Mulmuley、Vazirani、および Vazirani の分離補題

ランダムに選択された線形コスト関数を持つ任意の線形計画法は、高い確率で唯一の最適解を持つ。Mulmuley、Vazirani、およびVaziraniの分離補題は、この事実を任意の集合と、少数のランダムビットを用いてサンプリングされたランダムコスト関数に拡張する。
補題．とを正の整数とし、を宇宙 の任意の空でない部分集合族とする。宇宙の各要素が整数の重み を持ち、各要素が から独立かつ一様にランダムに選択されるとする。宇宙の集合Sの重みは次のように定義される 。 n {\displaystyle n} 北 {\displaystyle N} F {\displaystyle {\mathcal {F}}} { 1 、 … 、 n } {\displaystyle \{1,\dots ,n\}} × ∈ { 1 、 … 、 n } {\displaystyle x\in \{1,\dots ,n\}} わ （ × ） {\displaystyle w(x)} { 1 、 … 、 北 } {\displaystyle \{1,\dots ,N\}} F {\displaystyle {\mathcal {F}}}
わ （ S ） ＝ ∑ × ∈ S わ （ × ） 。 {\displaystyle w(S)=\sum _{x\in S}w(x)\,.}
すると、少なくとも の確率で、のすべての集合の中で最小の重みを持つ の唯一の集合が に存在します。 1 − n / 北 {\displaystyle 1-n/N} F {\displaystyle {\mathcal {F}}} F {\displaystyle {\mathcal {F}}}

この補題が族 の性質について何も仮定していないことは注目に値する。例えば、 はすべての空でない部分集合を含む可能性がある。 における各集合の重みはと の間であるため、平均すると、各可能な重みの集合が存在することになる。それでもなお、高い確率で、重みが最小となる唯一の集合が存在する。 F {\displaystyle {\mathcal {F}}} F {\displaystyle {\mathcal {F}}} 2 n − 1 {\displaystyle 2^{n}-1} F {\displaystyle {\mathcal {F}}} 1 {\displaystyle 1} n 北 {\displaystyle nN} （ 2 n − 1 ） / （ n 北 ） {\displaystyle (2^{n}-1)/(nN)}

マルムリー、バジラニ、およびバジラニの証明

要素xを除くすべての要素の重みを固定したと仮定する。この場合、 x は閾値重みαを持つ。つまり、 xの重みw ( x )がαより大きい場合、 x はどの最小重み部分集合にも含まれず、の場合、 x は最小重みの集合のいくつかに含まれる。さらに、の場合、すべての最小重み部分集合は必ずx を含むことに注意されたい（w(x)をαから減少させた場合、 x を含まない集合の重みは減少しないが、xを含む集合の重みは減少するからである）。したがって、最小重み部分集合がxを含むかどうかの曖昧性は、 xの重みがその閾値と正確に等しい場合にのみ発生する。この場合、 x を「特異」と呼ぶ。ここで、 xの閾値は他の要素の重みのみに基づいて定義されているため、 w(x)とは独立であり、したがって、w ( x ) が {1, …, N }から一様に選択される ため、 わ （ × ） ≤ α {\displaystyle w(x)\leq \alpha } わ （ × ） < α {\displaystyle w(x)<\alpha }

広報 [ ×  単数形 ] ＝ 広報 [ わ （ × ） ＝ α ] ≤ 1 / 北 {\displaystyle \Pr[x{\text{は特異である}}]=\Pr[w(x)=\alpha ]\leq 1/N}

そして、ある xが特異である確率は最大で n/Nである。特異な要素が存在しない場合、その時に限り、最小重み部分集合が一意に存在するので、補題は成立する。

注意: 一部のxには閾値がない 可能性があるので(つまり、 w ( x ) が最小値 1 を取得しても、 x はどの最小重みサブセットにも含まれない)、補題は (= ではなく) で成立します。 ≤ {\displaystyle \leq }

ジョエル・スペンサーの証明

これはジョエル・スペンサー（1995）による上記の証明の書き直し版である。[2]

集合内の 任意の要素xについて、定義する

α （ × ） ＝ 分 S ∈ F 、 × ∉ S わ （ S ） − 分 S ∈ F 、 × ∈ S わ （ S ∖ { × } ） 。 {\displaystyle \alpha (x)=\min _{S\in {\mathcal {F}},x\not \in S}w(S)-\min _{S\in {\mathcal {F}},x\in S}w(S\setminus \{x\}).}

はx以外の要素の重みのみに依存し、w ( x ) 自体には依存しないことに注意してください。したがって、 の値が何であれ、w ( x ) が{1, …, N }から一様に選択される場合 、 が に等しい確率は最大で1/ Nです。したがって、あるxに対して となる確率は最大で n/Nです。 α （ × ） {\displaystyle \alpha (x)} α （ × ） {\displaystyle \alpha (x)} α （ × ） {\displaystyle \alpha (x)} わ （ × ） ＝ α （ × ） {\displaystyle w(x)=\alpha (x)}

ここで、最小の重みを持つ2つの集合AとBがあるとすると、A\Bの任意のxを取ると、 F {\displaystyle {\mathcal {F}}}

α （ × ） ＝ 分 S ∈ F 、 × ∉ S わ （ S ） − 分 S ∈ F 、 × ∈ S わ （ S ∖ { × } ） ＝ わ （ B ） − （ わ （ あ ） − わ （ × ） ） ＝ わ （ × ） 、 {\displaystyle {\begin{aligned}\alpha (x)&=\min _{S\in {\mathcal {F}},x\not \in S}w(S)-\min _{S\in {\mathcal {F}},x\in S}w(S\setminus \{x\})\\&=w(B)-(w(A)-w(x))\\&=w(x),\end{aligned}}}

そして、これまで見てきたように、このイベントは最大で n/N の確率で発生します。

例/応用

  • 元々の応用は、グラフにおける最小重み（または最大重み）の完全マッチングでした。各辺には{1, …, 2 m }内のランダムな重みが割り当てられ、 は完全マッチングの集合であり、少なくとも1/2の確率で唯一の完全マッチングが存在します。グラフのTutte行列の各不定値を に置き換えると、 は辺のランダムな重みです。このとき、行列の行列式が非ゼロであることが示され、これを用いてマッチングを求めることができます。 F {\displaystyle {\mathcal {F}}} × 私 j {\displaystyle x_{ij}} 2 わ 私 j {\displaystyle 2^{w_{ij}}} わ 私 j {\displaystyle w_{ij}}
  • より一般的には、この論文では、「集合系 が与えられたとき、 内の集合 を見つける」という形式の探索問題は、「 内に総重量が最大でk以下の集合は存在するか？」という形式の決定問題に帰着できることも指摘されている。例えば、パパディミトリウとヤナカキスが提起した次の問題の解決方法が示されている。この問題は（論文執筆時点では）決定論的な多項式時間アルゴリズムが知られていない。グラフと「赤」とマークされた辺のサブセットが与えられたとき、ちょうどk 本の赤い辺を持つ完全マッチングを見つける。 （ S 、 F ） {\displaystyle (S,{\mathcal {F}})} F {\displaystyle {\mathcal {F}}} F {\displaystyle {\mathcal {F}}}
  • NP完全問題の一意解に関するヴァリアント・ヴァジラニ定理は、孤立補題を用いたより簡潔な証明を持つ。これは、CLIQUEからUNIQUE-CLIQUEへのランダム化帰着を与えることによって証明される。[ 3 ]
  • Ben-David、Chor & Goldreich (1989) は、平均ケースの複雑さに対する検索から決定への縮約において Valiant-Vazirani の証明を使用しています。
  • アヴィ・ウィグダーソンは1994年に孤立補題を用いてNLからULへのランダム還元を与え、NL/poly ⊆ ⊕L/polyであることを証明した。[4]ラインハルトとアレンダーは後に再び孤立補題を用いてNL/poly = UL/polyであることを証明した。[5]
  • ヘマスパアンドラとオギハラの著書には、一般化を含む分離技術に関する章があります。[6]
  • 分離補題はデジタル透かし方式の基礎として提案されている。[7]
  • 特定のケースにおいて分離補題を非ランダム化する研究[8]と、それを同一性検定に使用する研究が進行中である。[9]

注記

  1. ^ Noam Ta-Shma (2015); 孤立補題の簡単な証明、eccc
  2. ^ ジュクナ（2001）
  3. ^ マルムリー、ヴァジラニ、ヴァジラニ (1987)
  4. ^ ウィグダーソン（1994）
  5. ^ ラインハルト＆アレンダー（2000）
  6. ^ ヘマスパアンドラ＆荻原 (2002)
  7. ^ マジュムダール＆ウォン（2001）
  8. ^ アルヴィンド & ムコパディヤイ (2008)
  9. ^ アルヴィンド、ムコパディヤイ、スリニヴァサン (2008)

参考文献

  • Arvind, V.; Mukhopadhyay, Partha (2008). 分離補題のデランダム化と回路規模の下限値．近似、ランダム化、および組合せ最適化：アルゴリズムと手法に関する第11回国際ワークショップ APPROX 2008 および第12回国際ワークショップ RANDOM 2008 の議事録．米国マサチューセッツ州ボストン：Springer  - Verlag．pp . 276– 289．arXiv : 0804.0957．Bibcode : 2008arXiv0804.0957A．ISBN 978-3-540-85362-6. 2010年5月10日閲覧。
  • Arvind, V.; Mukhopadhyay, Partha; Srinivasan, Srikanth (2008). 非可換および可換多項式恒等式検定に関する新たな結果. 2008 IEEE 第23回計算複雑性年次会議論文集. IEEE Computer Society. pp.  268– 279. arXiv : 0801.0514 . Bibcode :2008arXiv0801.0514A. ISBN 978-0-7695-3169-4. 2010年5月10日閲覧。
  • Ben-David, S.; Chor, B .; Goldreich, O. (1989).平均事例複雑度の理論について. 第21回ACM計算理論シンポジウム議事録 - STOC '89. p. 204. doi :10.1145/73007.73027. ISBN 0897913078。
  • Calabro, C.; Impagliazzo, R.; Kabanets, V.; Paturi, R. (2008). 「一意なk-SATの計算量：k-CNFの分離補題」. Journal of Computer and System Sciences . 74 (3): 386. doi : 10.1016/j.jcss.2007.06.015 .
  • Chari, S.; Rohatgi, P.; Srinivasan, A. (1993).ランダムネス最適化による一意要素分離と完全マッチングおよび関連問題への応用. 第25回ACM計算理論シンポジウム - STOC '93の議事録. p. 458. doi :10.1145/167088.167213. hdl : 1813/6129 . ISBN 0897915917。
  • ヘマスパアンドラ、レーン・A.；オギハラ・ミツノリ（2002年）「第4章 分離技法」（PDF）複雑性理論コンパニオンシュプリンガーISBN 978-3-540-67419-1。
  • Majumdar, Rupak; Wong, Jennifer L. (2001).組合せ的分離補題を用いたSATの電子透かし. 第38回年次設計自動化会議議事録. ネバダ州ラスベガス, アメリカ合衆国: ACM. pp.  480– 485. CiteSeerX  10.1.1.16.9300 . doi :10.1145/378239.378566. ISBN 1-58113-297-2。
  • Reinhardt, K.; Allender, E. (2000). 「非決定性の明確化」（PDF） . SIAM Journal on Computing ( FTP ). p. 1118. doi :10.1137/S0097539798339041.[デッド FTP リンク] (ドキュメントを表示するには、ヘルプ:FTP を参照してください)
  • Mulmuley, ケタン州; Vazirani, ウメッシュ;ヴァジラニ、ビジェイ(1987)。 「マッチングは逆行列と同じくらい簡単です。」コンビナトリカ。7 (1): 105–113。CiteSeerX  10.1.1.70.2247。土井：10.1007/BF02579206。
  • ジュクナ、ステイシス (2001). 極限的組合せ論：コンピュータサイエンスへの応用. シュプリンガー. pp.  147– 150. ISBN 978-3-540-66313-3。
  • Valiant, L.; Vazirani, V. (1986). 「NPは一意解の検出と同じくらい簡単だ」(PDF) .理論計算機科学. 47 : 85–93 . doi : 10.1016/0304-3975(86)90135-0 .
  • Wigderson, Avi (1994). NL/poly ⊆ ⊕L/poly (PDF) . 第9回複雑性構造会議論文集. pp.  59– 62.
「https://en.wikipedia.org/w/index.php?title=Isolation_lemma&oldid=1292502348」より取得