Reductions to the set of random strings: the resource-bounded case

DOI10.2168/LMCS-10(3:5)2014zbMATH Open1338.68125arXiv1406.7658OpenAlexW1756533857MaRDI QIDQ2878751FDOQ2878751

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

Publication date: 5 September 2014

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1406.7658

Recommendations

• Reductions to the set of random strings: the resource-bounded case
• STACS 2004
• What can be efficiently reduced to the Kolmogorov-random strings?
• Limits on the Computational Power of Random Strings
• Limits on the computational power of random strings

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Cited In (13)

• The Complexity of Complexity
• Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
• On the Polynomial Depth of Various Sets of Random Strings
• What can be efficiently reduced to the Kolmogorov-random strings?
• Random strings and truth-table degrees of Turing complete c.e. sets
• Kolmogorov complexity, circuits, and the strength of formal theories of arithmetic
• Reductions to the set of random strings: the resource-bounded case
• On characterizations of randomized computation using plain Kolmogorov complexity
• On characterizations of randomized computation using plain Kolmogorov complexity
• Title not available (Why is that?)
• Limits on the Computational Power of Random Strings
• Lower bounds for reducibility to the Kolmogorov random strings
• Reduced word enumeration, complexity, and randomization

This page was built for publication: Reductions to the set of random strings: the resource-bounded case

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2878751)