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. We show that there exist languages in $DSPACE(f(n))$ which are random for the non-uniform class $DSPACE(g(n))/h(n)$, where $n$, $g(n)$ and $h(n)$ are in $o(f(n))$. Non-uniform complexity classes were introduced by Karp and Lipton and allow an advice string that depends only on the length of the input as additional information. This paper extends a result by Wilber who proved bounds for the existence of random languages for (uniform) time and space classes. Huynh provides a result for the special case of $P/poly$-random languages in $EXPSPACE$. Here we explore a different method using strings with high generalized Kolmogorov complexity. A characterization of the non-uniform space classes in terms of Kolmogorov complexity is given. This generalizes a result of Balcazar, Diaz, and Gabarro, where characterizations of the class $PSAPCE/poly$ are given.
Back to my homepage