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
Josef M. Breutzmann, Jack H. Lutz,
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.
Contents 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
Key words complexity classes, martingales, resource-bounded measure
Mathmatical Subject Classification 68Q15