# Equivalence of Measures of Complexity Classes

 Home  About  Browse  Search  Register  Subscriptions  Deposit Papers  Help

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.

 Full text available as: PostscriptAdobe PDF

## 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