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>REric Allender: The Strange Link between Incompressibility and Complexity < 10 > 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|}