Revision #1 Authors: Eric Allender, Harry Buhrman, Michal Koucký, Detlef Ronneburger, Dieter van Melkebeek

Accepted on: 16th May 2002 00:00

Downloads: 2819

Keywords:

We consider sets of strings with high Kolmogorov complexity, mainly

in resource-bounded settings but also in the traditional

recursion-theoretic sense. We present efficient reductions, showing

that these sets are hard and complete for various complexity classes.

In particular, in addition to the usual Kolmogorov complexity measure

K, we consider the time-bounded Kolmogorov complexity

measure KT that was introduced by Allender, as well

as a space-bounded measure KS, and Levin's time-bounded Kolmogorov

complexity Kt. Let R_K, R_KT, R_KS, R_Kt be the sets of

strings x having complexity at least |x|/2, according to each of

these measures. Our main results are:

o R_KS and R_Kt are complete for PSPACE and EXP, respectively,

under P/poly-truth-table reductions.

o EXP = NP^R_Kt.

o PSPACE = ZPP^R_KS, which is contained in P^R_K.

o The Discrete Log is in BPP^R_KT.

Our hardness results for EXP and PSPACE rely on nonrelativizing

proof techniques.

Our techniques also allow us to show that all recursively-enumerable

sets are reducible to RK via P/poly-truth-table reductions.

Our hardness result for PSPACE gives rise to fairly natural problems

that are complete for PSPACE under poly-time Turing reductions, but not

under logspace-many-one reductions.

In spite of the EXP- and PSPACE-completeness of R_Kt and R_KS, it

remains unknown if either of these problems is in logspace.

TR02-028 Authors: Eric Allender, Harry Buhrman, Michal Koucky, Detlef Ronneburger, Dieter van Melkebeek

Publication: 16th May 2002 09:23

Downloads: 4079

Keywords:

We consider sets of strings with high Kolmogorov complexity, mainly

in resource-bounded settings but also in the traditional

recursion-theoretic sense. We present efficient reductions, showing

that these sets are hard and complete for various complexity classes.

In particular, in addition to the usual Kolmogorov complexity measure

K, we consider the time-bounded Kolmogorov complexity

measure KT that was introduced by Allender, as well

as a space-bounded measure KS, and Levin's time-bounded Kolmogorov

complexity Kt. Let R_K, R_KT, R_KS, R_Kt be the sets of

strings x having complexity at least |x|/2, according to each of

these measures. Our main results are:

o R_KS and R_Kt are complete for PSPACE and EXP, respectively,

under P/poly-truth-table reductions.

o EXP = NP^R_Kt.

o PSPACE = ZPP^R_KS, which is contained in P^R_K.

o The Discrete Log is in BPP^R_KT.

Our hardness results for EXP and PSPACE rely on nonrelativizing

proof techniques.

Our techniques also allow us to show that all recursively-enumerable

sets are reducible to RK via P/poly-truth-table reductions.

Our hardness result for PSPACE gives rise to fairly natural problems

that are complete for PSPACE under poly-time Turing reductions, but not

under logspace-many-one reductions.

In spite of the EXP- and PSPACE-completeness of R_Kt and R_KS, it

remains unknown if either of these problems is in logspace.