Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR04-044 | 1st June 2004 00:00

What Can be Efficiently Reduced to the Kolmogorov-Random Strings?


Authors: Eric Allender, Harry Buhrman, Michal Koucky
Publication: 2nd June 2004 08:57
Downloads: 3077


We investigate the question of whether one can characterize complexity
classes (such as PSPACE or NEXP) in terms of efficient
reducibility to the set of Kolmogorov-random strings R_C.
We show that this question cannot be posed without explicitly dealing
with issues raised by the choice of universal
machine in the definition of Kolmogorov complexity. Among other results,
we show that although for every universal machine U, there are very
complex sets that are poly-time dtt-reducible to R_{C_U}, it is nonetheless true that
P = the set of all decidable sets in the intersection, over all
universal machines U, of the sets that are poly-time dtt-reducible to

We also show for a
broad class of reductions that the sets reducible to R_C have small
circuit complexity.

ISSN 1433-8092 | Imprint