Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Reducibility:
TR04-044 | 1st June 2004
Eric Allender, Harry Buhrman, Michal Koucky

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

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 ... more >>>

ISSN 1433-8092 | Imprint