Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR10-139 | 22nd June 2011 16:30

Limits on the Computational Power of Random Strings

RSS-Feed




Revision #1
Authors: Eric Allender, Luke Friedman, William Gasarch
Accepted on: 22nd June 2011 16:30
Downloads: 1555
Keywords: 


Abstract:

Let 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.



Changes to previous version:

Theorem 2.7 in the original version has been revised, and is now Proposition 5. New theorems (Theorems 4 and 11) have been added, making explicit some items that were discussed implicitly in the text of the original version. The exposition has been improved.


Paper:

TR10-139 | 17th September 2010 20:38

Limits on the Computational Power of Random Strings





TR10-139
Authors: Eric Allender, Luke Friedman, William Gasarch
Publication: 17th September 2010 20:38
Downloads: 1848
Keywords: 


Abstract:

Let 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.



ISSN 1433-8092 | Imprint