Portal de Periódicos da CAPES

Limits on the computational power of random strings

2012; Elsevier BV; Volume: 222; Linguagem: Inglês

10.1016/j.ic.2011.09.008

1090-2651

Eric Allender, Luke Friedman, William Gasarch,

semigroups and automata theory

How powerful is the set of random strings? What can one say about a set A that is efficiently reducible to R , the set of Kolmogorov-random strings? We present the first upper bound on the class of computable sets in P R and NP R . The two most widely-studied notions of Kolmogorov complexity are the “plain” complexity C ( x ) and “prefix” complexity K ( x ) ; this gives rise to two common ways to define the set of random strings “ R ”: R C and R K . (Of course, each different choice of universal Turing machine U in the definition of C and K yields another variant R C U or R K U .) Previous work on the power of “ R ” (for any of these variants) has shown: • BPP ⊆ { A : A ⩽ tt p R } . • PSPACE ⊆ P R . • NEXP ⊆ NP R . Since these inclusions hold irrespective of low-level details of how “ R ” is defined, and since BPP , PSPACE and NEXP are all in Δ 1 0 (the class of decidable languages), we have, e.g.: NEXP ⊆ Δ 1 0 ∩ ⋂ U NP R K U . Our main contribution is to present the first upper bounds on the complexity of sets that are efficiently reducible to R K U . We show: • BPP ⊆ Δ 1 0 ∩ ⋂ U { A : A ⩽ tt p R K U } ⊆ PSPACE . • NEXP ⊆ Δ 1 0 ∩ ⋂ U NP R K U ⊆ EXPSPACE . Hence, in particular, PSPACE is sandwiched between the class of sets polynomial-time Turing- and truth-table-reducible to R . As a side-product, we obtain new insight into the limits of techniques for derandomization from uniform hardness assumptions.