アーサー王と魔術師マーリン - 基盤(S)離散構造処理系プロジェクト

アーサー王と魔術師マーリン
～脱乱択化と回路計算量～
東京工業大学
河内 亮周
（Dan Gutfreund氏（IBM research, Haifa）との共同研究）
ERATO湊離散構造処理系＋NEO合同研究会 2010年7月30日
回路計算量と脱乱択化
～計算量理論の夢～
• 二つの重要なゴール
– 回路計算量の下界：難しそうな問題は小さな論理回路では計算で
きない？（NP≠P予想等）
– 脱乱択化：決定性計算と乱択計算の差はそれほど大きくない？
（BPP=P予想等）
• アーサー王と魔術師マーリンのお話でこの関係を説明します！
今回の登場人物
• アーサー王(King Arthur)
– 伝説のブリテン王．５～６世紀の実在の人物（ア
ンブロシウス・アウレリアヌス？）がモデルか？
– 戦乱のブリテン島に平和をもたらす．
• 魔術師マーリン(Wizard Merlin)
– ブリテンの魔術師．父が夢魔で母が貴族．
– アーサー王の補佐役．
NP問題
（アーサー王と魔術師マーリン登場前に）
• NP問題
– 非決定性Turing機械でpoly-time計算可能な問題
– 決定性poly-timeでは解けない問題もあると予想され
ている（NP≠P予想）
• 代表例：充足可能性問題（SAT）
– 入力：論理式φ
(x1, x2, x3) = (1,1,0)
– 出力：φが充足可能Yes, 充足不可能No
φ = x1 ∨ x2 ∧ ￢x3
Yes
非決定性 poly-time Turing機械
対話型証明系
• 計算モデルの一種 [Goldwasser, Micali & Rackoff, 1985]
• 証明者と検証者が通信して計算を行う．
– 入力がYesかNoのどちらかを正しく判定するのが目標．
– 証明者は検証者にYesと言わせたい！
入力：x
Yes
or
No
証明者
（無限の計算能力）
検証者
（決定性 or 乱択poly-time）
NP問題 in 対話証明
• NP問題（特にSAT）
1∨1∧￢0 = 1
入力：φ = x1 ∨ x2 ∧ ￢x3
入力φは充足可能です
証拠：(x1,x2,x3)= (1,1,0)
証明者
（無限の計算能力）
Yes
検証者
（決定性poly-time）
入力φが本当に充足可能ならば，
証明者が充足解を証拠とすることでYesと判定可能．
NP問題 in 対話証明
• NP問題（特にSAT）
1∧￢1∧1 = 0
入力：φ = x1 ∧ ￢x1 ∧ x2
入力φは充足可能です
証拠：(x1,x2)= (1,1)
証明者
（無限の計算能力）
No
検証者
（決定性poly-time）
入力φが実は充足不可能ならば，
証明者がどんな証拠を見せてもNoと判定可能
NP問題 in 対話型証明
• NP問題の定義 in 対話型証明
– 判定問題LがNPに属する⇔
x が Yes (x∈L) ↔ ∃証拠w: 検証者V(x,w) = Yes
入力：x
Yes
証拠
or
No
証明者P
（無限の計算能力）
検証者V
（決定性poly-time）
アーサー・マーリンゲーム
(Arthur-Merlin Game [Babai & Moran, 1986])
• NP問題に対する対話証明系の乱択的一般化
入力：x
乱数：r
マーリン
（無限の計算能力）
証拠：w
アーサー
（乱択poly-time）
Yes
or
No
• ある問題がアーサー・マーリンゲームで計算可能
⇔ Prr [ アーサー(x, r, w) が x を正しく判定] > 2/3
疑問：乱数は重要か？
• アーサー・マーリンゲームは本質的にNP計算
と同じではないか？
• 乱択アルゴリズムを効率良く決定性アルゴリ
ズムで模倣できないか？
脱乱択化
脱乱択化
(Derandomization)
• 乱択アルゴリズムを効率良く決定性アルゴリ
ズムで模倣できないか？
定理 [Impagliazzo & Wigderson, 1998]
回路計算量が指数関数的に高いあるクラスの問題が存在
任意の乱択アルゴリズムは
決定性アルゴリズムで効率良く模倣可能
回路計算量
• 関数（or 判定問題） f:{0,1}n→{0,1} の回路計算量
= fを計算する回路の最小素子数(AND, OR, NOT)
• 任意の関数は2n個以下の素子で計算可能,
i.e., 任意の関数の回路計算量 ≦2n
• P問題の回路計算量の上界は poly(n) （P ⊂ P/poly）
• NP問題（e.g., SAT）の回路計算量の下界が super-poly(n)
NP ≠ P
脱乱択化
(Derandomization)
• 乱択アルゴリズムを効率良く決定性アルゴリ
ズムで模倣できないか？
定理 [Impagliazzo & Wigderson, 1998]
決定性 exp-time で計算可能
exp-size 論理回路で計算不可能
な問題が存在
任意のpoly-time乱択アルゴリズムはpoly-time決定性アルゴリズムで模倣可能
(
)
(
)
E := DTIME 2O( n ) ⊄ SIZE 20.1n ⇒ BPP = P
アイデア: 擬似乱数生成器
ある程度の計算能力のアルゴリズムでは解けない問題が存在
計算の難しさからアルゴリズムを騙す擬似乱数を生成！
「どんなアルゴリズムも擬似乱数と真の乱数を効率良く区別できない」
アイデア: 擬似乱数生成器
決定性 exp-time で計算可能
exp-size 論理回路で計算不可能
な問題が存在
困難性増幅＋デザイン構成
poly(n)-time 計算可能な擬似乱数生成器Gが存在 s.t.
G:{0,1}O(log n) → {0,1}poly(n)
「どんなpoly-size回路もGの出力と真の乱数を区別できない」
poly-time 乱択アルゴリズム A(x,r) の模倣（入力：x，乱数：r）
A(x,G(00…0)), A(x,G(10…0)),…, A(x,G(11…1))を実行して多数決をとる．
2O(log n)=poly(n)
回路計算量と脱乱択化
～計算量理論の夢～
• 二つの重要なゴール
– 回路計算量の下界：難しそうな問題は小さな論理回路では計算できな
い？（NP≠P予想等）
– 脱乱択化：決定性計算と乱択計算の差はそれほど大きくない？（BPP=P
予想等）
回路計算量は脱乱択化の本質？
• 回路計算量の下界を証明するのは難しい！
• できれば避けたいが・・・
定理 [Kabanets & Impagliazzo, 2003]
乱択アルゴリズムが効率良く脱乱択化可能
あるクラスの問題がpoly-size論理回路で計算不可能
or
行列のパーマネントがpoly-size算術回路で計算不可能
回路計算量は脱乱択化の本質？
• 回路計算量の下界を証明するのは難しい！
• できれば避けたいが・・・
定理 [Kabanets & Impagliazzo, 2003]
乱択アルゴリズムが決定性アルゴリズムで効率良く模倣可能
あるNEXP問題がpoly-size論理回路で計算不可能
or
行列のパーマネントがpoly-size算術回路で計算不可能
BPP = P ⇒ NEXP ⊄ SIZE ( poly ( n ) ) ∨ PERM ∉ ASIZE ( poly ( n ) )
回路計算量と脱乱択化
～計算量理論の夢～
• 二つの重要なゴール
– 回路計算量の下界：難しそうな問題は小さな論理回路では計算できな
い？（NP≠P予想等）
– 脱乱択化：決定性計算と乱択計算の差はそれほど大きくない？（BPP=P
予想等）
アーサー・マーリンゲームの場合
• [Impagliazzo & Wigderson, 1998]の一般化
定理 [Klivans & van Melkebeek, 2001]
非決定性exp-timeで計算可能
非決定性exp-size論理回路で計算不可能
な問題が存在
アーサー・マーリンゲームは非決定性poly-timeで模倣可能
(
)
(
)
NE := NTIME 2O( n ) ⊄ NSIZE 20.1n ⇒ pr-AM = NP
AMゲームの脱乱択化にも
回路計算量が必要か？
定理 [Gutfreund & Kawachi, 2010]
AMゲームが効率良く脱乱択化可能
あるクラスの問題がexp-size論理回路では計算不可能
AMゲームの脱乱択化にも
回路計算量が必要か？
定理 [Gutfreund & Kawachi, 2010]
AMゲームがNP計算で模倣可能
NPオラクル付き決定性exp-timeで計算可能
exp-size論理回路で計算不可能
な問題が存在
(
pr-AM = NP ⇒ E NP ⊄ SIZE 20.1n
)
AMゲームの脱乱択化にも
回路計算量が必要か？
定理 [Gutfreund & Kawachi, 2010]
AMゲームがNPオラクル付き決定性poly-timeアルゴリズムで模倣可能
NPオラクル付き決定性exp-timeで計算可能
exp-size論理回路で計算不可能
な問題が存在
(
pr-AM ⊆ P NP ⇒ E NP ⊄ SIZE 20.1n
)
NPオラクル
• 問題LがPNPに属する⇔
∃NPオラクル付き決定性poly-time Turing機械 MNP
x ∈ L ↔ MNP(x) = 1
NPオラクル
Yes
x
or
決定性 poly-time Turing機械 M
No
導出される回路計算量の違い
定理 [Kabanets & Impagliazzo, 2003]
ある乱択アルゴリズムが効率良く脱乱択化可能
効率の良くない脱乱択化
あるクラスの問題がpoly-size論理回路で計算不可能
脱乱択化に使えない
or
行列のパーマネントがpoly-size算術回路で計算不可能
定理 [Gutfreund & Kawachi, 2010]
あるAMゲームが効率良く脱乱択化可能
効率の良い脱乱択化に十分
あるクラスの問題がexp-size論理回路では計算不可能
証明の方針
• 回路計算量の下界証明の方針
– 「下から」：計算能力の低いクラス
• e.g., 定数段poly-size論理回路ではPARITYは計算不可能
[Furst, Saxe & Sipser, 1982]
– 「上から」：計算能力の高いクラス
• e.g., 多項式時間階層(PH)のある問題はn100-size論理回
路では計算不可能[Kannan, 1984]
NPと多項式時間階層
• 問題 L が NP (=ΣP1) に属する
⇔ x ∈ L ↔ ∃w: P(x,w) = true
(P: poly-time 計算可能述語)
例：SAT
φ ∈ SAT ↔ ∃変数割当a: φ(a) = 1
よって SAT∈NP
poly-time 計算可能！
NPと多項式時間階層
• 問題 L が coNP (=ΠP1) に属する
⇔ x ∈ L ↔ ∀w: P(x,w) = true
(P: poly-time 計算可能述語)
例：UNSAT
φ ∈ UNSAT (φが充足不可能) ↔ ∀変数割当a: φ(a) = 0
よって UNSAT∈coNP
NPと多項式時間階層
• 問題 L が ΣP2 =NPNP に属する
⇔ x ∈ L ↔ ∃w1∀w2: P(x,w1,w2) = true
(P: poly-time 計算可能述語)
• 問題 L が ΠP2 =coNPNP に属する
⇔ x ∈ L ↔ ∀w1∃w2: P(x,w1,w2) = true
(P: poly-time 計算可能述語)
NPと多項式時間階層
• 問題 L が
ΣPi
P
Σ
に属する⇔ L ∈ NP i-1
∞
P ⇔
• 問題 L が PH に属する ⇔ L ∈∪
Σ
i
i=1
x∈L
↔ ∃w1∀w2,…,∃wk: P(x,w1,w2,…,wk) = true
(k: 定数，P: poly-time 計算可能述語)
PSPACE
PH
ΠP2
ΣP2
ΣP2∩ΠP2
(pr-)AM
PNP
NP
BPP
P
coNP
Kannanのアイデア
• PH はかなり複雑な問題を含むことができる
• 「小さい回路では計算できない」という性質を問題の
この問題HARDはPHに属し，
回路計算量はn100より大きい！
定義に埋め込む！
問題HARD
入力： x (長さ n)
出力： - YES if
∃n200-size 回路 C: {0,1}n→{0,1},
∀n100-size 回路 C’: {0,1}n→{0,1}
∃z: C’(z) ≠ C(z) (i.e., C’ は C を計算できない)
かつ C(x) = 1
- NO o.w.
より低いクラスへ
• （よりNPに近い）低いクラスで回路計算量の
下界を示したい！
定理 [Karp & Lipton, 1980]
もし poly-size 論理回路でSATが計算可能ならば PH = ΣP2∩ΠP2
PSPACE
PH
ΠP2
ΣP2
ΣP2∩ΠP2
(pr-)AM
PNP
NP
BPP
P
coNP
PSPACE
PH
=
ΣP2∩ΠP2
(pr-)AM
PNP
NP
BPP
P
coNP
より低いクラスへ
• （よりNPに近い）低いクラスで回路計算量の
下界を示したい！
定理 [Karp & Lipton, 1980]
もし poly-size 論理回路でSATが計算可能ならば PH = ΣP2∩ΠP2
• 場合分け
– SATがn100-size 回路で計算可能
• 問題HARD∈PH = ΣP2∩ΠP2 ，問題HARDが回路計算量
の下界n100を与える．
– SATがn100-size 回路で計算不可能
• 問題SAT∈NPが回路計算量の下界n100を与える．
定理 [Kannan, 1984]
∃問題 L ∈ ΣP2∩ΠP2 s.t. L は n100-size 論理回路では計算不可能
Kannan以降，「上から」の結果は以下の場合分けアプローチ
– SATがn100-size 回路で計算可能
• 問題HARD∈PH = ΣP2∩ΠP2 が難しい問題
– SATがn100-size 回路で計算不可能
• 問題SAT∈NP が難しい問題
一般化（n100-size superpoly-size）でどこまで高い下界が得られるか？
半指数関数 まで！[Miltersen, Vinodchandran & Watanabe, 1999]
f(n) が半指数関数 ⇔ f(f(n)) = 2O(n)
e.g., nlog nは半指数関数だが，2√nは違う．
半指数関数の壁を超えろ！
AMゲームの脱乱択化で
20.1n-size の下界！！
f(f(n)) = 2O(n)
我々のアプローチ
・・・やっぱり場合分け
だけど SAT が poly-size 回路 で計算できるかどうかで！
証明の概要
• SATが n100-size 回路で計算可能な場合
– 以前とだいたい同じ手法で証明可能．
– AMゲームオラクル付きpoly-time決定性計算でPHの計算が可能
（PH⊆Ppr-AM）[Chakaravathy & Roy, 2006]
NP
– 脱乱択化の仮定より Ppr-AM = PP = PNP
∴ HARD ∈ PNP
– 標準的な技法(padding)によりENP で exp-size 回路計算量の下界
証明の概要
• SATが n100-size 回路で計算不可能な場合
– 以前と同じ議論だと n100-size の下界しか得られない！
– 新しいアイデア
定理 [Fortnow, Pavan, and Sengupta, 2003]
∃SATの入力リスト (φ1,φ2,…,φp(n)) （|φi|=n）s.t. ∀n98-size 回路は
φ1,φ2,…,φp(n)のどれか一つで必ず間違える．(p(n) = poly(n))
– このリストはAMゲームオラクル付きpoly-time決定性計算で見つけら
れる（∴脱乱択化の仮定よりPNP計算で可能）
– このリストから難しい関数を定義する．
難しい関数の定義
定理 [Fortnow, Pavan, and Sengupta, 2003]
∃SATの入力リスト (φ1,φ2,…,φp(n)) （|φi|=n）s.t. ∀n98-size 回路は
φ1,φ2,…,φp(n)のどれか一つで必ず間違える．(p(n) = poly(n))
• 難しい関数として
f(i) := SAT(φi) =
1 if φi が充足可能
0 o.w.
と定義すると f: {0,1}m→{0,1} (入力長 m:=log(p(n)) = O(log n) に注意！）
• f は NPオラクル付き poly(n)-time = 2O(m)-time で計算可能でかつ poly(n)size = 2Ω(m)-size 回路では計算不可能！
• ∴ f の入力長mで見直すと，ENPで計算可能かつ指数関数的な回路計算
量下界を持つ！
まとめ
定理 [Gutfreund & Kawachi, 2010]
AMゲームがNPオラクル付き決定性poly-timeアルゴリズムで模倣可能
NPオラクル付き決定性exp-timeで計算可能
exp-size論理回路で計算不可能
な問題が存在
(
pr-AM ⊆ P NP ⇒ E NP ⊄ SIZE 20.1n
)