TY - GEN

T1 - Limits on the computational power of random strings

AU - Allender, Eric

AU - Friedman, Luke

AU - Gasarch, William

PY - 2011

Y1 - 2011

N2 - How powerful is the set of random strings? What can one say about a set A that is efficiently reducible to R, the set of Kolmogorov-random strings? We present the first upper bound on the class of computable sets in and . The two most widely-studied notions of Kolmogorov complexity are the "plain" complexity C(x) and "prefix" complexity K(x); this gives two ways to define the set "R": R C and R K . (Of course, each different choice of universal Turing machine U in the definition of C and K yields another variant or .) Previous work on the power of "R" (for any of these variants [1,2,9]) has shown . . . Since these inclusions hold irrespective of low-level details of how "R" is defined, we have e.g.: . ( is the class of computable sets.) Our main contribution is to present the first upper bounds on the complexity of sets that are efficiently reducible to . We show: . . Hence, in particular, is sandwiched between the class of sets Turing- and truth-table-reducible to R. As a side-product, we obtain new insight into the limits of techniques for derandomization from uniform hardness assumptions.

AB - How powerful is the set of random strings? What can one say about a set A that is efficiently reducible to R, the set of Kolmogorov-random strings? We present the first upper bound on the class of computable sets in and . The two most widely-studied notions of Kolmogorov complexity are the "plain" complexity C(x) and "prefix" complexity K(x); this gives two ways to define the set "R": R C and R K . (Of course, each different choice of universal Turing machine U in the definition of C and K yields another variant or .) Previous work on the power of "R" (for any of these variants [1,2,9]) has shown . . . Since these inclusions hold irrespective of low-level details of how "R" is defined, we have e.g.: . ( is the class of computable sets.) Our main contribution is to present the first upper bounds on the complexity of sets that are efficiently reducible to . We show: . . Hence, in particular, is sandwiched between the class of sets Turing- and truth-table-reducible to R. As a side-product, we obtain new insight into the limits of techniques for derandomization from uniform hardness assumptions.

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

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

U2 - 10.1007/978-3-642-22006-7_25

DO - 10.1007/978-3-642-22006-7_25

M3 - Conference contribution

AN - SCOPUS:79959983716

SN - 9783642220050

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 293

EP - 304

BT - Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings

T2 - 38th International Colloquium on Automata, Languages and Programming, ICALP 2011

Y2 - 4 July 2011 through 8 July 2011

ER -