新泽西州立罗格斯大学：The Strange Link between Incompressibility and Complexity

The Strange Link between Incompressibility and Complexity Eric Allender Rutgers University China Theory Week, Aarhus August 13, 2012

Eric Allender Rutgers University The Strange Link between Incompressibility and Complexity China Theory Week, Aarhus August 13, 2012

Today's Goal: > To present new developments in a line of research dating back to 2002, presenting some unexpected connections between Kolmogorov Complexity( the theory of randomness), and Computational Complexity Theory )Which ought to have nothing to do with each other! Eric Allender. The Strange Link between Incompressibility and Complexity 2>

Eric Allender: The Strange Link between Incompressibility and Complexity Today’s Goal:  To present new developments in a line of research dating back to 2002, presenting some unexpected connections between – Kolmogorov Complexity (the theory of randomness), and – Computational Complexity Theory Which ought to have nothing to do with each other!

Complexity Classes EXPSPACE NEXP PSPACE NP P/poly BPP P Eric Allender. The Strange Link between Incompressibility and Complexity

Eric Allender: The Strange Link between Incompressibility and Complexity Complexity Classes P NP BPP PSPACE NEXP EXPSPACE P/poly

A Jewel of derandomization >[Impagliazzo, Wigderson, 1997]: If there is a problem computable in time 2n that requires circuits of size 2En then p= BPP Eric Allender. The Strange Link between Incompressibility and Complexity 4>R

Eric Allender: The Strange Link between Incompressibility and Complexity A Jewel of Derandomization  [Impagliazzo, Wigderson, 1997]: If there is a problem computable in time 2n that requires circuits of size 2εn , then P = BPP

Randomness > Which of these sequences did I obtain by flipping a coin? 0101010101010101010101010101010 0110100111111100111000100101100 1101010001011100111111011001010 1=0.3183098861837906715377675267450 >Each of these sequences is equally likely, in the sense of probability theory - Which does not provide us with a way REaRer Ie t o talk about, "randomness".<5 RUGERS

Eric Allender: The Strange Link between Incompressibility and Complexity Randomness  Which of these sequences did I obtain by flipping a coin?  0101010101010101010101010101010  0110100111111100111000100101100  1101010001011100111111011001010  1/π =0.3183098861837906715377675267450 Each of these sequences is equally likely, in the sense of probability theory – which does not provide us with a way to talk about “randomness

Randomness > Which of these sequences did I obtain by flipping a coin? 0101010101010101010101010101010 0110100111111100111000100101100 1101010001011100111111011001010 1=0.3183098861837906715377675267450 > How many bits of information does each of these sequences contain? Eric Allender. The Strange Link between Incompressibility and Complexity

Eric Allender: The Strange Link between Incompressibility and Complexity Randomness  Which of these sequences did I obtain by flipping a coin?  0101010101010101010101010101010  0110100111111100111000100101100  1101010001011100111111011001010  1/π =0.3183098861837906715377675267450 How many bits of information does each of these sequences contain?

Kolmogorov Complexity >C()=mind: U(d)=X U is a "universal Turing machine >K(x)= mind: U(d)=X U is a universal prefix-free Turing machine Important property Invariance: The choice of the universal Turing machine U is unimportant (up to an additive constant) x is random if o(x)≥x Eric Allender. The Strange Link between Incompressibility and Complexity R

Eric Allender: The Strange Link between Incompressibility and Complexity Kolmogorov Complexity  C(x) = min{|d| : U(d) = x} – U is a “universal” Turing machine  K(x) = min{|d| : U(d) = x} – U is a “universal” prefix-free Turing machine  Important property – Invariance: The choice of the universal Turing machine U is unimportant (up to an additive constant).  x is random if C(x) ≥ |x|

Kolmogorov Complexity >C()=mind: U(d)=X U is a "universal Turing machine >K(x)= mind: U(d)=X U is a universal prefix-free Turing machine Important property Invariance: The choice of the universal Turing machine U is unimportant (up to an additive constant) x is random if o(x)≥|x,orK(x)≥冈 Eric Allender. The Strange Link between Incompressibility and Complexity

Eric Allender: The Strange Link between Incompressibility and Complexity Kolmogorov Complexity  C(x) = min{|d| : U(d) = x} – U is a “universal” Turing machine  K(x) = min{|d| : U(d) = x} – U is a “universal” prefix-free Turing machine  Important property – Invariance: The choice of the universal Turing machine U is unimportant (up to an additive constant).  x is random if C(x) ≥ |x|, or K(x) ≥ |x|

KC and randomness >K(x and C(x) are close C(x)≤K()≤C(x)+2log|x Two notions of randomness Rc={:C(x)≥|X} Rk={x:K(x)≥} >.. actually, infinitely many notions of randomness R UX: Cu(x)2(] Eric Allender. The Strange Link between Incompressibility and Complexity R

Eric Allender: The Strange Link between Incompressibility and Complexity K, C, and Randomness  K(x) and C(x) are “close”: – C(x) ≤ K(x) ≤ C(x) + 2 log |x|  Two notions of randomness: – RC = {x : C(x) ≥ |x|} – RK = {x : K(x) ≥ |x|}  …actually, infinitely many notions of randomness: – RCU = {x : CU(x) ≥ |x|}

KC and randomness >K(x and C(x) are close C(x)≤K()≤C(x)+2log|x Two notions of randomness Rc={:C(x)≥|X} Rk={x:K(x)≥} >.. actually, infinitely many notions of randomness RCu=(X: Cu()=Xl),RKu=(x: Ku(x)2xlh Eric Allender. The Strange Link between Incompressibility and Complexity 10>R

Eric Allender: The Strange Link between Incompressibility and Complexity K, C, and Randomness  K(x) and C(x) are “close”: – C(x) ≤ K(x) ≤ C(x) + 2 log |x|  Two notions of randomness: – RC = {x : C(x) ≥ |x|} – RK = {x : K(x) ≥ |x|}  …actually, infinitely many notions of randomness: – RCU = {x : CU(x) ≥ |x|}, RKU = {x : KU(x) ≥ |x|}