Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR02-028 | 16th May 2002 00:00

Power from Random Strings Revision of: TR02-028

RSS-Feed

Abstract:


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.


Paper:

TR02-028 | 15th May 2002 00:00

Power from Random Strings


Abstract:

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.


Comment(s):

Comment #1 to TR02-028 | 6th March 2024 17:15

A Comment Regarding KT and Circuit Size





Comment #1
Authors: Eric Allender, Dieter van Melkebeek
Accepted on: 6th March 2024 17:15
Downloads: 125
Keywords: 


Abstract:

This short note provides a clarification of the relationship between circuit size and KT complexity.




ISSN 1433-8092 | Imprint