ECCC-Report TR12-054https://eccc.weizmann.ac.il/report/2012/054Comments and Revisions published for TR12-054en-usMon, 30 Jun 2014 17:06:24 +0300
Revision 1
| Reductions to the set of random strings:the resource-bounded case |
Eric Allender,
Harry Buhrman,
Luke Friedman,
Bruno Loff
https://eccc.weizmann.ac.il/report/2012/054#revision1This 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 by [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.Mon, 30 Jun 2014 17:06:24 +0300https://eccc.weizmann.ac.il/report/2012/054#revision1
Paper TR12-054
| Reductions to the set of random strings:the resource-bounded case |
Eric Allender,
Harry Buhrman,
Luke Friedman,
Bruno Loff
https://eccc.weizmann.ac.il/report/2012/054This 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 by [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.Wed, 02 May 2012 11:48:21 +0300https://eccc.weizmann.ac.il/report/2012/054