Equivalence of Measures of Complexity Classes

Thumbnail Image
Date
1996
Authors
Breutzmann, Josef
Lutz, Jack
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Authors
Research Projects
Organizational Units
Organizational Unit
Journal Issue
Is Version Of
Versions
Series
Department
Computer Science
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.

Comments
Description
Keywords
Citation
DOI
Source
Subject Categories
Copyright
Collections