Non-uniform complexity classes and random languages
M. Mundhenk, Rainer Schuler · 2002
A language A is considered to be random for a class C if for every language B in C the fraction of the strings where A and B coincide is approximately 1/2. R.E. Wilber (1983) showed that there exist tight space and time hierarchies of random languages. These results are extended to nonuniform complexity classes, and a result of D.T. Huynh (1987) proving that there exist languages in EXPSPACE which are random for P/poly, is generalized. It is shown that there exist languages in P/poly which are random for DSPACE (f(n)) for every function f(n).>