Equivalence of Measures of Complexity Classes

Breutzmann, Josef M. and Lutz, Jack H. (1996) Equivalence of Measures of Complexity Classes. Technical Report TR96-11, 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 resource-bounded 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
polynomial-time computable sequence beta, beta_1, beta_2, ...  of real
numbers (biases) \beta_i in [delta, 1-delta], and any complexity class
C (such as P, NP, BPP, P/Poly, PH, PSPACE, etc.)  that is closed under
positive, polynomial-time, truth-table reductions with queries of at
most linear length, it is shown that the following two conditions are
equivalent.
(1)   C has p-measure 0 (respectively, measure 0 in E,
measure 0 in E_2) relative to the coin-toss probability
measure given by the sequence beta.
(2)   C has p-measure 0 (respectively, measure 0 in
E, measure 0 in E_2) relative to the uniform probability
measure.


Subjects:
All uncategorized technical reports


ID code:
00000131
Deposited by:
Staff Account on 30 September 1996





Contact site administrator at: ssg@cs.iastate.edu