|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
20 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Derandomizing from Random Strings | | Harry Buhrman
; Lance Fortnow
; Michal Koucký
; Bruno Loff
; | | Date: |
16 Dec 2009 | | Abstract: | 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. | | Source: | arXiv, 0912.3162 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER