TY - JOUR

T1 - What can be efficiently reduced to the Kolmogorov-random strings?

AU - Allender, Eric

AU - Buhrman, Harry

AU - Koucký, Michal

N1 - Funding Information:
We would like to thank Rod Downey, Troy Lee, Joe Miller, and Kolya Vereshchagin for helpful discussions. The first and third author acknowledge the support of NSF grant CCR-0104823. Part of this work was done while the third author was visiting CWI, Amsterdam while he was a graduate student at Rutgers University, NJ.

PY - 2006/3

Y1 - 2006/3

N2 - 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 RC. This question arises because PSPACE ⊆ PRC and NEXP ⊆ NPRC, and no larger complexity classes are known to be reducible to RC in this way. 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. What follows is a list of some of our main results. • Although Kummer showed that, for every universal machine U there is a time bound t such that the halting problem is disjunctive truth-table reducible to RCU in time t, there is no such time bound t that suffices for every universal machine U. We also show that, for some machines U, the disjunctive reduction can be computed in as little as doubly-exponential time. • Although for every universal machine U, there are very complex sets that are ≤dttP-reducible to RCU, it is nonetheless true that P = REC ∩ ∩U {A: A ≤dttP RCU}. (A similar statement holds for parity-truth-table reductions.) • Any decidable set that is polynomial-time monotone-truth-table reducible to RC is in P/poly. • Any decidable set that is polynomial-time truth-table reducible to RC via a reduction that asks at most f (n) queries on inputs of size n lies in P/(f (n)2f(n)3logf(n)).

AB - 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 RC. This question arises because PSPACE ⊆ PRC and NEXP ⊆ NPRC, and no larger complexity classes are known to be reducible to RC in this way. 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. What follows is a list of some of our main results. • Although Kummer showed that, for every universal machine U there is a time bound t such that the halting problem is disjunctive truth-table reducible to RCU in time t, there is no such time bound t that suffices for every universal machine U. We also show that, for some machines U, the disjunctive reduction can be computed in as little as doubly-exponential time. • Although for every universal machine U, there are very complex sets that are ≤dttP-reducible to RCU, it is nonetheless true that P = REC ∩ ∩U {A: A ≤dttP RCU}. (A similar statement holds for parity-truth-table reductions.) • Any decidable set that is polynomial-time monotone-truth-table reducible to RC is in P/poly. • Any decidable set that is polynomial-time truth-table reducible to RC via a reduction that asks at most f (n) queries on inputs of size n lies in P/(f (n)2f(n)3logf(n)).

KW - Computational complexity

KW - Kolmogorov complexity

KW - Polynomial-time reducibility

UR - http://www.scopus.com/inward/record.url?scp=33644815433&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33644815433&partnerID=8YFLogxK

U2 - 10.1016/j.apal.2005.06.003

DO - 10.1016/j.apal.2005.06.003

M3 - Article

AN - SCOPUS:33644815433

SN - 0168-0072

VL - 138

SP - 2

EP - 19

JO - Annals of Pure and Applied Logic

JF - Annals of Pure and Applied Logic

IS - 1-3

ER -