An upward measure separation theorem

Let E denote the exponential time complexity class \(E=DTIME(2^{lin})\) and let ESPACE denote the exponential space complexity class \(ESPACE=DSPACE(2^{lin})\). Let BPP denote the bounded-error probabilistic polynomial time complexity class. Let P/Poly denote the nonuniform complexity class of all languages in P which have polynomial size circuits. The old downward separation result \(E\subsetneqq ESPACE\Rightarrow P\subsetneqq PSPACE\) of [\textit{R. V. Book}, Comparing complexity classes, J. Comput. Syst. Sci. 9, 213-229 (1974)], had been improved to the following two results in [\textit{J. Hartmanis}, \textit{Y. Yesha}, Computation times of NP sets of different densities, Theor. Comp. Sci. 34, 17-32 (1984)]: (1) \(P\subsetneqq P/Poly\cap PSPACE \Leftrightarrow\) \(E\subsetneqq ESPACE,\) (2) \(P\subsetneqq BPP\Rightarrow E\subsetneqq ESPACE.\) This paper refines (2) in a measure-theoretic sense: \underbar{Theorem}: IF \(P\subsetneqq BPP\) then \(\mu\) (E\(| ESPACE)=0\). (This means that E is a measure 0 subset of ESPACE in the resource-bounded measure theory of \textit{J. H. Lutz} [Almost everywhere high nonuniform complexity, Proc. 4th Structure in complexity Theory Conf. 81-91 (1989)] and [Category and measure in complexity classes, SIAM J. Comput. 19, 1100-1131 (1990; Zbl 0711.68046)]).

Recommendations

Cites work

Cited in

(4)

This page was built for publication: An upward measure separation theorem

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