An upward measure separation theorem
type: Item
instance of: scholarly article
title: An upward measure separation theorem
zbMATH Open document ID: 0732.68042
DOI: 10.1016/0304-3975(91)90320-2
author: Jack H. Lutz
published in: Theoretical Computer Science
publication date: 1991-01-01T00:00:00Z
review text: 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)]).
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 4211494
reviewed by: Andreas Brandstädt
MaRDI profile type: MaRDI publication profile
full work available at URL: 0304-3975(91)90320-2
OpenAlex ID: W1970373826
cites work: Q4039803
cites work: Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
cites work: Comparing complexity classes
cites work: On the Length of Programs for Computing Finite Binary Sequences
cites work: A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
cites work: Q4065548
cites work: Families of recursive predicates of measure zero
cites work: Computational Complexity of Probabilistic Turing Machines
cites work: Q5726943
cites work: Q3751001
cites work: Computation times of NP sets of different densities
cites work: On the notion of infinite pseudorandom sequences
cites work: Q3214803
cites work: Algorithms and Randomness
cites work: Randomness conservation inequalities; information and independence in mathematical theories
cites work: Category and Measure in Complexity Classes
cites work: Q4770482
cites work: Hardness vs randomness
cites work: A formal theory of inductive inference. Part II
Recommended article: Category and Measure in Complexity Classes
Recommended article: Resource-bounded measure on probabilistic classes
Recommended article: Upward separations and weaker hypotheses in resource-bounded measure
Recommended article: Q4266481
Recommended article: Q4501523
Recommended article: Martingale families and dimension in P
Recommended article: A stronger Kolmogorov zero-one law for resource-bounded measure
Recommended article: Q4258588
Recommended article: Logical Approaches to Computational Barriers
Recommended article: Relative to a random oracle, NP is not small
description: scientific article; zbMATH DE number 4211494