TR04-044 Authors: Eric Allender, Harry Buhrman, Michal Koucky

Publication: 2nd June 2004 08:57

Downloads: 2107

Keywords:

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

R_{C_U}.

We also show for a

broad class of reductions that the sets reducible to R_C have small

circuit complexity.