KC and randomness ) When it makes no difference, We'l write“R” instead of r or r >Basic facts R is undecidable but it is not "easy to use it as an oracle R is not NP-hard under poly-time sm reductions, unless P=NP Things get more interesting when we consider more powerful types of reducibility Eric Allender. The Strange Link between Incompressibility and Complexity <11>REric Allender: The Strange Link between Incompressibility and Complexity < 11 > K, C, and Randomness  When it makes no difference, we’ll write “R” instead of RC or RK.  Basic facts: – R is undecidable – …but it is not “easy” to use it as an oracle. – R is not NP-hard under poly-time ≤m reductions, unless P=NP. – Things get more interesting when we consider more powerful types of reducibility