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