Derandomizing from Random Strings

Details Derandomizing from Random Strings Derandomizing from Random Strings

2009-12-16

arxiv.org/abs/0912.3162v1

Computer Science

Computational Complexity

Scientific paper

In this paper we show that BPP is truth-table reducible to the set of Kolmogorov random strings R_K. It was previously known that PSPACE, and hence BPP is Turing-reducible to R_K. The earlier proof relied on the adaptivity of the Turing-reduction to find a Kolmogorov-random string of polynomial length using the set R_K as oracle. Our new non-adaptive result relies on a new fundamental fact about the set R_K, namely each initial segment of the characteristic sequence of R_K is not compressible by recursive means. As a partial converse to our claim we show that strings of high Kolmogorov-complexity when used as advice are not much more useful than randomly chosen strings.

Affiliated with

Also associated with

No associations

Rating

Derandomizing from Random Strings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Derandomizing from Random Strings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Derandomizing from Random Strings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-49165