ECCC-Report TR10-139https://eccc.weizmann.ac.il/report/2010/139Comments and Revisions published for TR10-139en-usWed, 22 Jun 2011 16:30:32 +0300
Revision 1
| Limits on the Computational Power of Random Strings |
Eric Allender,
Luke Friedman,
William Gasarch
https://eccc.weizmann.ac.il/report/2010/139#revision1Let C(x) and K(x) denote plain and prefix Kolmogorov complexity, respectively, and let R_C and R_K denote the sets of strings that are ``random'' according to these measures; both R_K and R_C are undecidable. Earlier work has shown that every set in NEXP is in NP relative to both R_K and R_C, and that every set in BPP is polynomial-time truth-table reducible to both R_K and R_C [Allender, Buhrman, Koucky],[Buhrman,Fortnow,Koucky,Loff].
(All of these inclusions hold, no matter which
``universal'' Turing machine one uses in the definitions of C(x) and K(x).) Since each machine U gives rise to a slightly different measure C_U or K_U, these inclusions can be stated as:
** BPP is contained in \DEC intersect \bigcap_U {A : A \pttred R_{C_U}}.
** NEXP is contained in \DEC intersect \bigcap_U NP^{R_{C_U}}.
** BPP is contained in \DEC intersect \bigcap_U {A : A \pttred R_{K_U}}.
** NEXP is contained in \DEC intersect \bigcap_U NP^{R_K_U}.
(Here, \DEC denotes the class of decidable sets.)
It remains unknown whether \DEC is EQUAL to \DEC intersect \bigcap_U {A : A \pttred R_C_U}.
In this paper, we present the first upper bounds on the complexity of sets that are efficiently reducible to R_K. We show:
** BPP \subseteq \DEC \cap \bigcap_U {A : A \pttred R_K_U} \subseteq PSPACE.
** NEXP \subseteq \DEC \cap \bigcap_U NP^{R_K_U}\subseteq EXPSPACE.
This also provides the first quantitative limits on the applicability of uniform derandomization techniques.Wed, 22 Jun 2011 16:30:32 +0300https://eccc.weizmann.ac.il/report/2010/139#revision1
Paper TR10-139
| Limits on the Computational Power of Random Strings |
Eric Allender,
Luke Friedman,
William Gasarch
https://eccc.weizmann.ac.il/report/2010/139Let C(x) and K(x) denote plain and prefix Kolmogorov complexity, respectively, and let R_C and R_K denote the sets of strings that are ``random'' according to these measures; both R_K and R_C are undecidable. Earlier work has shown that every set in NEXP is in NP relative to both R_K and R_C, and that every set in BPP is polynomial-time truth-table reducible to both R_K and R_C [Allender, Buhrman, Koucky],[Buhrman,Fortnow,Koucky,Loff].
(All of these inclusions hold, no matter which
``universal'' Turing machine one uses in the definitions of C(x) and K(x).) Since each machine U gives rise to a slightly different measure C_U or K_U, these inclusions can be stated as:
** BPP is contained in \DEC intersect \bigcap_U {A : A \pttred R_{C_U}}.
** NEXP is contained in \DEC intersect \bigcap_U NP^{R_{C_U}}.
** BPP is contained in \DEC intersect \bigcap_U {A : A \pttred R_{K_U}}.
** NEXP is contained in \DEC intersect \bigcap_U NP^{R_K_U}.
(Here, \DEC denotes the class of decidable sets.)
It remains unknown whether \DEC is EQUAL to \DEC intersect \bigcap_U {A : A \pttred R_C_U}.
In this paper, we present the first upper bounds on the complexity of sets that are efficiently reducible to R_K. We show:
** BPP \subseteq \DEC \cap \bigcap_U {A : A \pttred R_K_U} \subseteq PSPACE.
** NEXP \subseteq \DEC \cap \bigcap_U NP^{R_K_U}\subseteq EXPSPACE.
This also provides the first quantitative limits on the applicability of uniform derandomization techniques.Fri, 17 Sep 2010 20:38:56 +0200https://eccc.weizmann.ac.il/report/2010/139