Advertisement
Published in:
2012 | OriginalPaper | Chapter
Reductions to the Set of Random Strings: The Resource-Bounded Case
Authors : Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff
Published in: Mathematical Foundations of Computer Science 2012
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
This paper is motivated by a conjecture [1,5] 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 [5] 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.