Report

Circuit Complexity and Derandomization Tokyo Institute of Technology Akinori Kawachi Layout • Randomized vs Determinsitic Algorithms – Primality Test • General Framework for Derandomization – Circuit Complexity Derandomization • Circuits – Circuit Complexity and NP vs. P • Necessity of Circuit Complexity for Derandomization • Summary Deterministic v.s. Randomized Algorithms for (Decision) Problems Randomness is useful for real-world computation! n = input length Decision problem: PRIME Input: n-bit number x (0 ≤ x < 2n) Output: “Yes” if x ∈ PRIME (x is prime) “No” otherwise Exponential-time speed-up! Elementary Det. algorithm: O(2n/2) time [Eratosthenes, B.C. 2c] Rand. algorithm: O(n3) time w/ succ. prob. 99% [Miller 1976, Rabin 1980] Deterministic v.s. Randomized Algorithms for (Decision) Problems How much randomness make computation strong? Decision problem: PRIME Input: n-bit number x (0 ≤ N < 2n) Output: “Yes” if x ∈ PRIME (x is prime) “No” otherwise Polynomial-time slow-down Rand. algorithm: O(n3) time w/ succ. prob. 99% [Miller 1976, Rabin 1980] Det. algorithm: O(n12) time [Agrawal, Kayal & Saxena 2004 Gödel Prize] Derandomization Conjecture Always poly-time derandomization possible? Conjecture BPP = P Randomization yields NO exponential speed-up! P = {problem: poly-time det. TM computes} BPP = {problem: poly-time prob. TM computes w/ bounded errors} Class BPP Class BPP (Bounded-error Prob. Poly-time) L∈BPP Def x∊L x∉L Prr[A(x,r) = Yes] > 2/3 Prr[A(x,r) = No] > 2/3 r is uniform over {0,1}m m = |r| = poly(|x|) A(・,・): poly-time det. TM Nondeterministic Version Conjecture AM = NP Class AM (Arthur-Merlin Games) L∈AM Def x∊L x∉L Prr[∃w: A(x,w,r) = Yes] > 2/3 Prr[∀w: A(x,w,r) = No] > 2/3 |r|,|w| = poly(|x|) A(・,・,・): poly-time det. TM Hardness vs. Randomness Trade-offs [Yao ’82, Blum & Micali ’84] • Hard problem exists Similar theorem holds Good Pseudo-RandominGenerator (PRG) exists. nondet. version (AM=NP) [Klivans & van Melkebeek 2001] • Simulate randomized algorithms det.ly with PRG! Theorem [Impagliazzo & Wigderson 1998] ∃2O()-time computable decision problem H s.t. no 20.1-size circuit can compute for every BPP = P (L is computed in prob. poly-time w/ bounded errors L is computed in det. poly-time) Circuit Gate set = {∧, ∨, ￢, 0, 1} ∨ ∧ ∧ ∨ ∧ x1 ￢ x2 x3 0 Circuit 1 Gate set = {∧, ∨, ￢, 0, 1} 1∨0 = 1 ∨ 0∧1 = 0 0 1 ∧ 1 0 1∧0 = 0 ∧ 1 1∧1 = 1 ∨ 0 0 ∧ Input = (1,1,0) 1 1 0∨1 = 1 1 ￢0 = 1 ￢ 1 1 0 0 0 Size = 7 Depth = 5 Circuit Complexity Size of circuits is measure for computational resource! Definition s(n)-size circuit family {Cn:{0,1}n→{0,1}}n computes L Def x ∈ L C|x|(x) = 1 x ∉ L C|x|(x) = 0 & size of Cn ≤ s(n) Circuit complexity of L := min { size of circuit family computing L } Computational Power of Circuits Theorem [Lupanov 1970] Circuit complexity of any problem = O(2n/n) any (even non-recursive) problem can be computed by some O(2n/n)-size circuit family. SIZE(poly) = {problem: poly-size circuit family can compute} Theorem [Fisher & Pippenger 1979] P ⊂ SIZE(poly) Poly-time TM can be simulated by poly-size circuit family. NP vs. P and Circuits Conjecture NP ≠ P Some NP problem cannot be computed by any poly-time TM. Conjecture NP ⊄ SIZE(poly) Some NP problem has superpoly circuit complexity. Note: NP ⊄ SIZE(poly) NP ≠ P Proving super-poly circuit complexity in NP solves NP vs. P! Current Status Randomized version of NEXP (Buhrman, Fortnow, & Thierauf 1998) Theorem MA-EXP ⊄ SIZE(poly) Theorem (Williams 2011) Const-depth poly-size w/ Modulo gates NEXP ⊄ ACC0(poly) Grand Challenge NEXP ⊄ SIZE(poly) Cf. H-R tradeoff for BPP=P requires at least EXP ⊄ SIZE(2.1n)! Hardness vs. Randomness Trade-offs [Yao ’82, Blum & Micali ’84] • Hard problem exists Good Pseudo-Random Generator (PRG) exists. • Simulate randomized algorithms det.ly with PRG! Theorem [Impagliazzo & Wigderson 1998] ∃2O()-time computable decision problem H s.t. no 20.1-size circuit can compute for every BPP = P (L is computed in prob. poly-time w/ bounded errors L is computed in det. poly-time) Proof Sketch 1. Construct PRG from hard H. 2. Simulate rand. algo. w/ p-random bits. Proof Sketch 1. Construct PRG from hard H. Goal: Construct GH: {0,1}O(log m) → {0,1}m For every poly-size circuit C, Prs[ C(GH(s)) = 1 ] ≈ Prr[ C(r) = 1 ] Pseudo-random! truly random! Proof: ∃good distinguisher D for GH ∃small circuit CD for H Point # possible s = 2O(log m) = poly(m) # possible r = 2m Proof Sketch 2. Simulate rand. algo. w/ p-random bits. Goal: Det.ly simulate rand. algo. by GH L∈BPP Def x∊L x∉L Prr[A(x,r) = Yes] > 2/3 Prr[A(x,r) = No] > 2/3 |r| = poly(|x|) A(・,・): poly-time det. TM Proof Sketch 2. Simulate rand. algo. w/ p-random bits. Goal: Det.ly simulate rand. algo. by GH Trivial Simulation Enumerate all possible -bit strings! A(x,00…00) A(x,00…01) #Yes > 2 ∙ 2 3 #No > 2 ∙ 2 3 x∊L x∉L = = No A(x,11…10) A(x,11…11) Require O(2m)=O(2poly(n)) time… Yes Yes = = Yes … Proof Sketch 2. Simulate rand. algo. w/ p-random bits. Goal: Det.ly simulate rand. algo. by GH Simulation w/ GH A(x,・) = circuit C Enumerate all possible log -bit seeds of GH! A(x,GH(0…0)) … = = A(x,G (1…1)) Require 2O(log m) =H poly(n) time! No Yes #Yes > 3 ∙ 2 4 log #No > 3 ∙ 2 4 log x∊L x∉L Is Circuit Complexity Essential? • Proving “some problem is really hard” is HARD! (e.g. NP≠P) – It’s the ultimate goal in complexity theory… • Can avoid “proving hardness” for derandomization? NO! Derandomization implies proving hardness!! Theorem [Kabanets & Impagliazzo ‘03] BPP=P Some problem is hard. Theorem [Gutfreund & Kawachi ‘10, Aaronson, Aydinlioglu, Buhrman, Hitchcock, & van Melkebeek ‘11] prAM ⊆ NP Some problem is extremely hard. Theorem [Kabanets & Impagliazzo ‘03] BPP = P NEXP ⊄ SIZE poly , or Permanent ∉ ASIZE poly Resolving “arithmetic-circuit version of NP vs. P“ Theorem [Gutfreund & Kawachi ‘10, Aaronson, Aydinlioglu, Buhrman, Hitchcock, & van Melkebeek ‘11] prAM ⊆ NP EXPNP ⊄ SIZE 20.1 Summary • Proving circuit complexity Derandomization – through Pseudo-Random Generator – BPP = P, AM = NP, and more… • Derandomization Proving circuit complexity Proving Circuit Complexity ≈ Derandomization