

Breutzmann, Josef M. and Lutz, Jack H. (1996) Equivalence of Measures of Complexity Classes. Technical Report TR9611, Department of Computer Science, Iowa State University.
Abstract
Equivalence of Measures of Complexity Classes
Josef M. Breutzmann Jack H. Lutz
Department of Mathematics Department of Computer Science
and Computer Science Iowa State University
Wartburg College Ames, Iowa 50011
Waverly, Iowa 50677
The resourcebounded measures of complexity classes are shown to be
robust with respect to certain changes in the underlying probability
measure. Specifically, for any real number delta > 0, any uniformly
polynomialtime computable sequence beta, beta_1, beta_2, ... of real
numbers (biases) \beta_i in [delta, 1delta], and any complexity class
C (such as P, NP, BPP, P/Poly, PH, PSPACE, etc.) that is closed under
positive, polynomialtime, truthtable reductions with queries of at
most linear length, it is shown that the following two conditions are
equivalent.
(1) C has pmeasure 0 (respectively, measure 0 in E,
measure 0 in E_2) relative to the cointoss probability
measure given by the sequence beta.
(2) C has pmeasure 0 (respectively, measure 0 in
E, measure 0 in E_2) relative to the uniform probability
measure.
Contact site administrator at: ssg@cs.iastate.edu
