Abstract für Paper
Autor: Martin Mundhenk and R. Schuler
Journal of Complexity, 1991
Abstract:
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 g(n) and h(n) are in o(f(n)), and f(n) is o(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 ppoly-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 et al where characterizations of the class
psppoly are given.
Kontaktadresse: schuler@informatik.uni-ulm.de