Publication Date

1996

Technical Report Number

TR96-11

Subjects

Mathematics of Computing

Abstract

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.

Share

COinS