The MathNet Korea
Information Center for Mathematical Science

### 논문검색

Information Center for Mathematical Science

#### 논문검색

SIAM Journal on Computing
( Vol. 29 NO.1 / (1999))
Equivalence of Measures of Complexity Classes

Pages. 302-326
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 $vec{eta}=(eta_0, eta_1, eta_2,...)$ of real numbers (biases) $eta_i in [delta , 1-delta]$, and for any complexity class $mathcal{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.egin{itemize}item[(1)] $mathcal{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 $vec{eta}$.item[(2)] $mathcal{C}$ has p-measure 0 (respectively, measure 0 in E, Measure 0 in E$_2$) relative to the uniform probability measure. end {itemize} hspace{0.3cm} The proof introduces three techniques that may be useful in other contexts, namely, (i) the transformation of an efficient martingale for one probability measure into an efficient martingale for a ""nearby"" probability measure; (ii) the construction of a {it positive bias reduction}, a truth-table reduction that encodes a positive, efficient, approximate simulation of one bias sequence by another; and (iii) the use of such a reduction to {it dilate} an efficient martingale for the simulated probability measure into an efficient martingale for the simulating probability measure. 1. Introduction 2. Preliminaries 3. Resource-bounded $\nu$-measure 4. Summable equivalence 5. Exact computation 6. Martingale dilation 7. Positive bias reduction 8. Equivalence for complexity classes 9. Conclusion complexity classes, martingales, resource-bounded measure 68Q15