本記事は
-
PCP定理とその証明 (紹介編)
-
PCP定理とその証明 (準備編)
の続きで, PCP定理の証明の全体像を説明します. 細かい解析などは後の記事で行います. この分野を専門的に学ぶ必要がない限りは本記事まで把握していれば良いと思います. 「エクスパンダー性がどのように効いてくるのか?」などについては以降の記事を読む必要があります.
PCP定理
ある定数, 多項式, 有限集合と, 与えられた2-CSPのインスタンスを以下の性質を満たす別の2-CSPのインスタンスに変換する多項式時間アルゴリズムが存在する: 任意の2-CSPインスタンスに対し,
- の変数の個数をとすると, の変数の個数は高々.
- のアルファベットは.
簡単な復習
これまで, 2-CSPに対して制約グラフと呼ばれる概念を定義しました.
2-CSPの制約グラフ(前回の記事の定義2の再掲)
以下を満たすを制約グラフと呼ぶ:
- は構造グラフと呼ばれる無向グラフであり, は変数の集合に対応する. 頂点集合はなどと番号付けされており, それに基づいて順序が定まっている.
- は有限集合であり, アルファベットと呼ばれる. 変数にはの要素が代入される.
- 各辺には制約と呼ばれる集合が対応しており, がを満たすとき, は制約を満たすという.
関数を割当といい,
を割当によって充足されない制約の割合とし, とする. ここではがよりも(上の順序の意味で)前にありを順序対として扱っている.
制約グラフのサイズを
で定めます (とには依存しません).
ステップ1ではUNSATの値をさほど変えずに構造グラフを正則エクスパンダーに変換できることを示しました.
(前回の記事の定理4の再掲)
ある定数が存在して, 任意の制約グラフが与えられたときに以下の性質を満たす制約グラフを出力する決定的多項式時間アルゴリズムが存在する:
以後, 簡単のためにグラフに対する諸概念を制約グラフに対して当てはめて呼びます. 例えば「-正則制約グラフ」と言った場合, その構造グラフの正則性を意味します.
UNSATの倍化
定理1はUNSATの値を倍化するという次の定理から証明できます.
ある有限集合が存在して次が成り立つ: 任意のアルファベットに対してある二つの定数が存在して, 与えられた制約グラフに対して多項式時間で別の制約グラフが構成できて以下の三つの条件を満たす:
端的に言えば, 制約グラフをUNSAT値を倍になるよう効率的に変換できるという定理です. 充足不能な制約グラフは常にが成り立つので, ギャップ増幅定理を回だけ適用すればにできます.
(定理3を仮定した上で定理1を証明)
与えられた2-CSPのインスタンスを表す制約グラフに対して定理3を回適用して得られる制約グラフをとする. すなわち, とし, に定理3を適用して構成される制約グラフをと定義する.
各はアルファベット上の2-CSPであり, なので, に対してとなります. この定数はアルファベットにのみ依存するのでuniversal constantとすることができる. また, である.
従ってこのに対応する2-CSPは定理1の主張を確かに満たす.
定理3の証明は次の三つの構成要素からなります:
- 構造グラフをスパースかつエクスパンダーにする
- ギャップ増幅
- アルファベット削減
前回の記事では一つ目について解説しました. 本記事では残りの二つについて解説します.
ギャップ増幅補題
定理3の証明へのチャレンジとして, 次の方針を考えてみます.
方針: アルファベットの増大
アルファベットサイズを(元の制約グラフのサイズに依存して)十分大きくすることが許されるならば, ギャップ増幅は容易です. 元の制約グラフをとします. を以下で定めます:
- 変換後のグラフを上の完全グラフとします.
- 変換後のアルファベットをとします. 割り当てと頂点に対し, は関数とみなします.
- 変換後の制約を定義します. 割り当ては次の条件を満たすとき, の辺における制約を満たすとします: 関数としてであり, さらには元の制約グラフのの全ての制約を満たす.
元の制約グラフがならば, その充足割り当てを使っての充足割り当てが構成できるためです. 一方でならば, どの割り当てを使っても全ての辺が充足されないためとなります. 完全グラフに変換する方法は確かにギャップを増幅しています.
しかしこの構成は定理3の証明にはなりえません. というのも, この構成によって得られる制約グラフのアルファベットはその要素数が元のグラフに依存してしまうからです. 定理3では, 元のグラフが如何に大きくても同じアルファベット上の制約グラフに変換することが要請されていることに注意が必要です.
制約グラフの冪乗
ギャップ増幅ではグラフの冪乗と呼ばれる操作によって与えられる制約グラフを考えます. 一般にグラフの冪乗と言えばそのグラフの隣接行列の冪乗を指す概念です. グラフおよびに対し, 個の頂点からなる列は全てのが辺をなすときにからへの-ウォークと呼び, 特に二頂点をそれぞれ始点,終点と呼びます. ここではは順序付きのタプルですが, グラフは無向グラフなので順序を反転させたタプルもまたからへの-ウォークになっています.
冪乗グラフとは全ての長さのウォークの端点間に辺を追加して得られるグラフです. 同じ二頂点間に長さのウォークが二通り以上存在する場合はその個数(逆向きのウォークは数えない)分だけ多重辺にします. 元のグラフが-正則ならばは-正則です (ここでは多重辺はその分だけ次数をカウントしているため, 隣接点がちょうど個あるわけではないことに注意).
グラフとの例. 太線は2本の多重辺を持つことを意味する.
制約グラフに対する冪乗操作を定めるためにいくつか準備をします. -正則な制約グラフを考え, その頂点集合に番号付けをしてとし, に全順序をつけます (このときの順序はどのようなものでも構いません). このとき, 各頂点の隣接点集合にも頂点番号に基づいて順序が定まります. こうすることで, 頂点の番目の隣接点を定めることができます. 同様にに対してもの隣接頂点集合に順序がつきます.
次の定義がこの記事(ひいてはDinur PCPの理解)における最も重要な概念ですので, 長いですが確実に理解しましょう.
(制約グラフの冪乗)
-正則な制約グラフとに対し, 制約グラフを以下で定義する:
- グラフは冪乗で定める. 記法の単純化のため, 以下ではとする.
- アルファベットは. 割り当てに対し, 各を関数に対応させる. この関数はの番目の頂点にを割り当てる関数である. なお, に対してはこの対応関係に影響しないので, 一対一対応関係ではない. 頂点に割り当てられた値をとし, これをのに対する意見と呼ぶ.
- の各辺の制約は, 二頂点の値が次の条件を満たすかつその時に限り, はの制約を満たすとする: 任意のを満たすに対し, が元のグラフの制約を満たす.
初見だとイメージがわかりずらいかもしれませんが, 次の図が参考になると思います.
頂点に割り当てられた値はの各頂点にの元を割り当てる関数とみなす (上). それぞれ頂点を中心とした距離にある二つの円を考え, それらの間にあるの辺に対応する制約を全て満たしていれば, はに対応する制約を満たす.
の辺は長さのウォークの端点であり, 制約の構成では半径の円を考えているので, 必ず二つの円は(幾何的な意味での)交わりを持ちます. しかし一般に円上の二点の間に必ずしも辺があるとは限りません(その場合は辺は任意の割り当てで充足されると定義します).
実際には, 前処理として補題2を適用して構造グラフを自己ループ付きのエクスパンダーに変換してから冪乗操作を行います. 従って(長さのウォークは自己ループもとりうるので)実際には長さ以下のウォークを全て考えるため, 円上でというよりは球上の頂点を考える方がイメージとしては適切です.
元の制約グラフがならば, です. 実際, の充足割り当ての一つをとしたときに, なる任意のを考えると球内の任意の二頂点間の元の制約が満たされるため, となることがわかります.
ではであった時はどうなるでしょうか? 元の制約グラフが自己ループを持つ正則エクスパンダーならばが増幅することが示せます.
(ギャップ増幅補題)
を任意の定数とする. これら三つのみに依存するある定数が存在して以下が成り立つ: -正則-エクスパンダーである任意の制約グラフに対し,
アルファベット削減
パラメータをくらいにとっておけば補題4よりとなります. 一見するとこれで定理3を示せていそうに見えますが, のアルファベットはその要素数が元のアルファベットに依存してしまうため証明になっていません. そこでアルファベットサイズをに依存しない定数まで削減する必要があります. このパートをアルファベット削減(alphabet reduction)と言います.
(アルファベット削減補題)
あるアルファベットと二つの定数が存在して次が成り立つ:
任意の制約グラフを多項式時間で別の制約グラフに変換できては以下を満たす:
ここではアルファベットと定数は与えられた制約グラフに依存しないことに注意してください.
補題5は当時すでに知られていた手法から(専門家にとっては)容易に証明できる内容なのですが, その証明には誤り訂正符号やassignment tester (PCP of proxity) といった概念を要するので初学者にとっては厳しい道のりになるでしょう.
各種補題の仮定の下でのPCP定理の証明
エクスパンダー化(補題2), ギャップ増幅補題(補題4), アルファベット削減補題(補題5)の仮定の下で定理3を証明します. 定理3がPCP定理(定理1)を導出することは既に示してありますので, これらの補題からPCP定理が導出できます.
(補題2,4,5定理3)
与えられた制約グラフをとする.
下図のように補題2,4,5をこの順に適用して制約グラフを変換していく.
ギャップ増幅補題を適用する際のパラメータはあとで適切に設定する.
補題2,4,5を適用して制約グラフを変換していく.
この一連の変換では, ならばであることは容易に確認できます.
ギャップ増幅補題(補題4)を適用する際, パラメータをとすると, 最終的に得られる制約グラフは
となる. 従って, とすれば定理3のに関する主張を満たすことになる. なお, 各パラメータの従属関係を図示すると以下となる:
パラメータの従属関係
ここで, は与えられた制約グラフのアルファベットサイズであるものの, それ以外のは他の何にも依存しないuniversal constantです. サイズに関しても
となり, はuniversal constantであり, はにのみ依存する.
従って, 最終的に得られる制約グラフは確かに定理3の主張を満たす.