Allender, Eric and Buhrman, Harry and Friedman, Luke and Loff, Bruno - Reductions to the set of random strings: The resource-bounded case

lmcs:723 - Logical Methods in Computer Science, August 19, 2014, Volume 10, Issue 3
Reductions to the set of random strings: The resource-bounded case

Authors: Allender, Eric and Buhrman, Harry and Friedman, Luke and Loff, Bruno

This paper is motivated by a conjecture that BPP can be characterized in terms of polynomial-time nonadaptive reductions to the set of Kolmogorov-random strings. In this paper we show that an approach laid out in [Allender et al] to settle this conjecture cannot succeed without significant alteration, but that it does bear fruit if we consider time-bounded Kolmogorov complexity instead. We show that if a set A is reducible in polynomial time to the set of time-t-bounded Kolmogorov random strings (for all large enough time bounds t), then A is in P/poly, and that if in addition such a reduction exists for any universal Turing machine one uses in the definition of Kolmogorov complexity, then A is in PSPACE.


Source : oai:arXiv.org:1406.7658
DOI : 10.2168/LMCS-10(3:5)2014
Volume: Volume 10, Issue 3
Published on: August 19, 2014
Submitted on: November 6, 2012
Keywords: Computer Science - Computational Complexity,Computer Science - Logic in Computer Science


Share

Consultation statistics

This page has been seen 57 times.
This article's PDF has been downloaded 21 times.