0

PCP定理とその証明 (証明概要編)

260
0

本記事は

  1. PCP定理とその証明 (紹介編)
  2. PCP定理とその証明 (準備編)

の続きで, PCP定理の証明の全体像を説明します. 細かい解析などは後の記事で行います. この分野を専門的に学ぶ必要がない限りは本記事まで把握していれば良いと思います. 「エクスパンダー性がどのように効いてくるのか?」などについては以降の記事を読む必要があります.

PCP定理

ある定数c>0,kN, 多項式p:NN, 有限集合Σ0と, 与えられた2-CSPのインスタンスCを以下の性質を満たす別の2-CSPのインスタンスCに変換する多項式時間アルゴリズムが存在する: 任意の2-CSPインスタンスCに対し,

  • UNSAT(C)=0UNSAT(C)=0
  • UNSAT(C)>0UNSAT(C)c
  • Cの変数の個数をnとすると, Cの変数の個数は高々p(n).
  • CのアルファベットはΣ0.

簡単な復習

これまで, 2-CSPに対して制約グラフと呼ばれる概念を定義しました.

2-CSPの制約グラフ(前回の記事の定義2の再掲)

以下を満たすG=((V,E),Σ,C)制約グラフと呼ぶ:

  • (V,E)構造グラフと呼ばれる無向グラフであり, Vは変数の集合に対応する. 頂点集合VV={v1,,vn}などと番号付けされており, それに基づいて順序が定まっている.
  • Σは有限集合であり, アルファベットと呼ばれる. 変数にはΣの要素が代入される.
  • 各辺eEには制約と呼ばれる集合c(e)Σ×Σが対応しており, (a,b)Σ×Σ(a,b)c(e)を満たすとき, (a,b)は制約c(e)を満たすという.

関数σ:VΣ割当といい,
UNSAT(G,σ)=|{uvE:(σ(u),σ(v))c(uv)}||E|
を割当σによって充足されない制約の割合とし, UNSAT(G)=min{UNSAT(G,σ):σΣV}とする. ここで{u,v}uvよりも(V上の順序の意味で)前にあり(σ(u),σ(v))を順序対として扱っている.

制約グラフG=((V,E),Σ,C)サイズ
size(G)=|V|+|E|
で定めます (ΣCには依存しません).

ステップ1ではUNSATの値をさほど変えずに構造グラフを正則エクスパンダーに変換できることを示しました.

(前回の記事の定理4の再掲)

ある定数λ<1,dN,c>0,β>0が存在して, 任意の制約グラフG=((V,E),Σ,C)が与えられたときに以下の性質を満たす制約グラフG=((V,E),Σ,C)を出力する決定的多項式時間アルゴリズムが存在する:

  • (V,E)は自己ループを持つd-正則なλ-エクスパンダー.
  • |V|c|E|.
  • UNSAT(G)UNSAT(G)βUNSAT(G).

以後, 簡単のためにグラフに対する諸概念を制約グラフに対して当てはめて呼びます. 例えば「d-正則制約グラフ」と言った場合, その構造グラフ(V,E)の正則性を意味します.

UNSATの倍化

定理1はUNSATの値を倍化するという次の定理から証明できます.

ある有限集合Σ0が存在して次が成り立つ: 任意のアルファベットΣに対してある二つの定数c>0,0<α<1が存在して, 与えられた制約グラフG=((V,E),Σ,C)に対して多項式時間で別の制約グラフG=((V,E),Σ0,C)が構成できて以下の三つの条件を満たす:

  • size(G)csize(G)
  • UNSAT(G)=0ならばUNSAT(G)=0
  • UNSAT(G)min(α,2UNSAT(G)))

端的に言えば, 制約グラフをUNSAT値を倍になるよう効率的に変換できるという定理です. 充足不能な制約グラフGは常にUNSAT(G)1/|E|が成り立つので, ギャップ増幅定理をO(log(|E|))回だけ適用すればUNSAT(G)αにできます.

(定理3を仮定した上で定理1を証明)

与えられた2-CSPのインスタンスを表す制約グラフGに対して定理3をi回適用して得られる制約グラフをGiとする. すなわち, G0=Gとし, Giに定理3を適用して構成される制約グラフをGi+1と定義する.

GiはアルファベットΣ0上の2-CSPであり, UNSAT(Gi)min(2i/|E|,α)なので, i=log2(|E|)に対してUNSAT(Gi)αとなります. この定数αはアルファベットΣ0にのみ依存するのでuniversal constantとすることができる. また, size(Gi)cisize(G)poly(size(G))である.
従ってこのGiに対応する2-CSPは定理1の主張を確かに満たす.

定理3の証明は次の三つの構成要素からなります:

  1. 構造グラフをスパースかつエクスパンダーにする
  2. ギャップ増幅
  3. アルファベット削減

前回の記事では一つ目について解説しました. 本記事では残りの二つについて解説します.

ギャップ増幅補題

定理3の証明へのチャレンジとして, 次の方針を考えてみます.

方針: アルファベットの増大

アルファベットサイズを(元の制約グラフのサイズに依存して)十分大きくすることが許されるならば, ギャップ増幅は容易です. 元の制約グラフをG=((V,E),Σ,C)とします. G=((V,E),Σ,C)を以下で定めます:

  • 変換後のグラフ(V,E)V上の完全グラフとします.
  • 変換後のアルファベットをΣ=ΣVとします. 割り当てσ:VΣと頂点uVに対し, σ(u)Σは関数σ(u):VΣとみなします.
  • 変換後の制約Cを定義します. 割り当てσ:VΣは次の条件を満たすとき, Gの辺e={u,v}における制約を満たすとします: 関数としてσ(u)=σ(v)であり, さらにσ(u):VΣは元の制約グラフのCの全ての制約を満たす.

元の制約グラフGUNSAT(G)=0ならば, その充足割り当てを使ってGの充足割り当てが構成できるためUNSAT(G)=0です. 一方でUNSAT(G)>0ならば, どの割り当てを使っても全ての辺が充足されないためUNSAT(G)=1となります. 完全グラフに変換する方法は確かにギャップを増幅しています.

しかしこの構成は定理3の証明にはなりえません. というのも, この構成によって得られる制約グラフのアルファベットΣ=ΣVはその要素数が元のグラフに依存してしまうからです. 定理3では, 元のグラフが如何に大きくても同じアルファベットΣ0上の制約グラフに変換することが要請されていることに注意が必要です.

制約グラフの冪乗

ギャップ増幅ではグラフの冪乗と呼ばれる操作によって与えられる制約グラフを考えます. 一般にグラフの冪乗と言えばそのグラフの隣接行列の冪乗を指す概念です. グラフG=(V,E)およびZ0に対し, +1個の頂点からなる列(u0,u1,,u)は全てのui,ui+1が辺をなすときにu0からuへの-ウォークと呼び, 特に二頂点u0,uをそれぞれ始点,終点と呼びます. ここでは(u0,,u)は順序付きのタプルですが, グラフは無向グラフなので順序を反転させたタプル(u,,u0)もまたuからu0への-ウォークになっています.

冪乗グラフGとは全ての長さのウォークの端点間に辺を追加して得られるグラフです. 同じ二頂点間に長さtのウォークが二通り以上存在する場合はその個数(逆向きのウォークは数えない)分だけ多重辺にします. 元のグラフGd-正則ならばGd-正則です (ここでは多重辺はその分だけ次数をカウントしているため, 隣接点がちょうどd個あるわけではないことに注意).
グラフ!FORMULA[124][36833][0]と!FORMULA[125][35453837][0]の例. 太線は2本の多重辺を持つことを意味する. グラフGG2の例. 太線は2本の多重辺を持つことを意味する.

制約グラフに対する冪乗操作を定めるためにいくつか準備をします. d-正則な制約グラフGを考え, その頂点集合Vに番号付けをしてV={v1,,vn}とし, Vに全順序をつけます (このときの順序はどのようなものでも構いません). このとき, 各頂点uの隣接点集合NG(u)にも頂点番号に基づいて順序が定まります. こうすることで, 頂点uj番目の隣接点を定めることができます. 同様にGに対してもuの隣接頂点集合NG(u)に順序がつきます.

次の定義がこの記事(ひいてはDinur PCPの理解)における最も重要な概念ですので, 長いですが確実に理解しましょう.

(制約グラフの冪乗)

d-正則な制約グラフG=((V,E),Σ,C)tNに対し, 制約グラフGt=((V,E),Σ,C)を以下で定義する:

  • グラフ(V,E)は冪乗(V,E)=(V,E)tで定める. 記法の単純化のため, 以下ではΓ(u)=NGt/2(u)とする.
  • アルファベットΣΣ=Σdt/2. 割り当てσ:VΣに対し, 各σ(u)=(a1,,adt/2)Σdt/2を関数σ(u):Γ(u)Σに対応させる. この関数はΓ(u)i番目の頂点にaiΣを割り当てる関数である. なお, i>|Γ(u)|に対してaiはこの対応関係に影響しないので, 一対一対応関係ではない. 頂点vΓ(u)に割り当てられた値をσ(u)vとし, これをuvに対する意見と呼ぶ.
  • Gの各辺e={u,v}Eの制約は, 二頂点u,vの値a,bΣが次の条件を満たすかつその時に限り, (a,b)eの制約を満たすとする: 任意の{u~,v~}Eを満たすu~Γ(u),v~Γ(v)に対し, (au~,bv~)Σ2が元のグラフの制約c({u~,v~})を満たす.

初見だとイメージがわかりずらいかもしれませんが, 次の図が参考になると思います.
頂点!FORMULA[169][38259][0]に割り当てられた値!FORMULA[170][37639][0]は!FORMULA[171][-404021683][0]の各頂点に!FORMULA[172][838988151][0]の元を割り当てる関数とみなす (上). それぞれ頂点!FORMULA[173][36778281][0]を中心とした距離!FORMULA[174][-1912477639][0]にある二つの円を考え, それらの間にある!FORMULA[175][36833][0]の辺に対応する制約を全て満たしていれば, !FORMULA[176][-1173451986][0]は!FORMULA[177][-393664998][0]に対応する制約を満たす. 頂点uに割り当てられた値aΓ(u)=NGt/2(u)の各頂点にΣの元を割り当てる関数とみなす (上). それぞれ頂点u,vを中心とした距離t/2にある二つの円を考え, それらの間にあるGの辺に対応する制約を全て満たしていれば, (a,b)e={u,v}に対応する制約を満たす.

Gtの辺e={u,v}は長さtのウォークの端点であり, 制約Cの構成では半径t/2の円を考えているので, 必ず二つの円は(幾何的な意味での)交わりを持ちます. しかし一般に円上の二点の間に必ずしも辺があるとは限りません(その場合は辺eは任意の割り当てで充足されると定義します).

実際には, 前処理として補題2を適用して構造グラフを自己ループ付きのエクスパンダーに変換してから冪乗操作を行います. 従って(長さt/2のウォークは自己ループもとりうるので)実際には長さt/2以下のウォークを全て考えるため, 円上でというよりは球上の頂点を考える方がイメージとしては適切です.

元の制約グラフがUNSAT(G)=0ならば, UNSAT(Gt)=0です. 実際, Gの充足割り当ての一つをσ:VΣとしたときに, σ(u)v=σ(v)なる任意のσを考えると球内の任意の二頂点間の元の制約が満たされるため, UNSAT(Gt)=0となることがわかります.

ではUNSAT(G)>0であった時はどうなるでしょうか? 元の制約グラフGが自己ループを持つ正則エクスパンダーならばUNSAT(Gt)が増幅することが示せます.

(ギャップ増幅補題)

λ,d,|Σ|を任意の定数とする. これら三つのみに依存するある定数β=β(λ,d,|Σ|)>0が存在して以下が成り立つ: d-正則λ-エクスパンダーである任意の制約グラフG=((V,E),Σ,C)に対し,
UNSAT(Gt)βtmin(UNSAT(G),1t).

アルファベット削減

パラメータtN2/βくらいにとっておけば補題4よりUNSAT(Gt)2UNSAT(G)となります. 一見するとこれで定理3を示せていそうに見えますが, GtのアルファベットΣはその要素数が元のアルファベットΣに依存してしまうため証明になっていません. そこでアルファベットサイズをGに依存しない定数まで削減する必要があります. このパートをアルファベット削減(alphabet reduction)と言います.

(アルファベット削減補題)

あるアルファベットΣ0と二つの定数β,c>0が存在して次が成り立つ:
任意の制約グラフG=((V,E),Σ,C)を多項式時間で別の制約グラフG=((V,E),Σ0,C)に変換できてGは以下を満たす:

  • size(G)csize(G).
  • βUNSAT(G)UNSAT(G)UNSAT(G)

ここではアルファベットΣ0と定数β,cは与えられた制約グラフGに依存しないことに注意してください.
補題5は当時すでに知られていた手法から(専門家にとっては)容易に証明できる内容なのですが, その証明には誤り訂正符号やassignment tester (PCP of proxity) といった概念を要するので初学者にとっては厳しい道のりになるでしょう.

各種補題の仮定の下でのPCP定理の証明

エクスパンダー化(補題2), ギャップ増幅補題(補題4), アルファベット削減補題(補題5)の仮定の下で定理3を証明します. 定理3がPCP定理(定理1)を導出することは既に示してありますので, これらの補題からPCP定理が導出できます.

(補題2,4,5定理3)

与えられた制約グラフをG=((V,E),Σ,C)とする.
下図のように補題2,4,5をこの順に適用して制約グラフを変換していく.
ギャップ増幅補題を適用する際のパラメータtはあとで適切に設定する.
補題2,4,5を適用して制約グラフを変換していく. 補題2,4,5を適用して制約グラフを変換していく.
この一連の変換では, UNSAT(G)=0ならばUNSAT(G5)=0であることは容易に確認できます.
ギャップ増幅補題(補題4)を適用する際, パラメータtt=4(β5β4β2)2とすると, 最終的に得られる制約グラフG5
UNSAT(G5)β5UNSAT(G4)β5β4tmin(UNSAT(G2),1t)β5β4tmin(β2UNSAT(G),1t)2min(UNSAT(G),1t)
となる. 従って, α=2/tとすれば定理3のUNSAT(G)に関する主張を満たすことになる. なお, 各パラメータの従属関係を図示すると以下となる:
パラメータの従属関係 パラメータの従属関係
ここで, |Σ|は与えられた制約グラフのアルファベットサイズであるものの, それ以外のβ5,λ2,β2,d2は他の何にも依存しないuniversal constantです. サイズに関しても
size(G5)c5size(G4)c5d2tsize(G2)c2c5d2tsize(G)
となり, c2,c5はuniversal constantであり, t|Σ|にのみ依存する.

従って, 最終的に得られる制約グラフG5は確かに定理3の主張を満たす.

投稿日:2024814
更新日:2024815
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

knewknowl
knewknowl
22
5930
東工大助教. 理論計算機科学.

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. 簡単な復習
  2. UNSATの倍化
  3. ギャップ増幅補題
  4. 方針: アルファベットの増大
  5. 制約グラフの冪乗
  6. アルファベット削減
  7. 各種補題の仮定の下でのPCP定理の証明