Equivalence of Measures of Complexity Classes.
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 \ldots )$ of real numbers (biases) $\beta_i \in [\delta, 1-\delta]$, and for any complexity class ${\bf \cal 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) ${\bf \cal C}$ has p-measure 0 (respectively, measure 0 in E, measure 0 in E2) relative to the coin-toss probability measure given by the sequence ${\mv{\beta}}$.(2) ${\bf \cal C}$ has p-measure 0 (respectively, measure 0 in E, measure 0 in E 2) relative to the uniform probability measure. 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  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 dilate an efficient martingale for the simulated probability measure into an efficient martingale for the simulating probability measure.
Introduction
In the 1990's, the measure-theoretic study of complexity classes has yielded
a growing body of new, quantitative insights into various much-studied aspects
of computational complexity. Benefits of this study to date include
improved bounds on the densities of hard languages [15]; newly discovered
relationships among circuit-size complexity, pseudorandom generators, and
natural proofs [21]; strong new hypotheses that may have sufficient explanatory
power (in terms of provable, plausible consequences) to help unify our
present plethora of unsolved fundamental problems [18, 15, 7, 16, 11]; and
a new generalization of the completeness phenomenon that dramatically
enlarges the set of computational problems that are provably strongly intractable
[14, 6, 2, 7, 8, 1]. See [13] for a survey of these and related developments

Intuitively, suppose that a language A ' f0; 1g   is chosen according to
a random experiment in which an independent toss of a fair coin is used
to decide whether each string is in A. Then classical Lebesgue measure
theory (described in [5, 20], for example) identifies certain measure 0 sets
X of languages, for which the probability that A 2 X in this experiment
is 0. Effective measure theory, which says what it means for a set of decidable
languages to have measure 0 as a subset of the set of all such lan-
guages, has been investigated by Freidzon [4], Mehlhorn [19], and others.
The resource-bounded measure theory introduced by Lutz [12] is a powerful
generalization of Lebesgue measure. Special cases of resource-bounded
measure include classical Lebesgue measure; a strengthened version of effective
measure; and most importantly, measures in
polynomial ), and other complexity classes. The small subsets
of such a complexity class are then the measure 0 sets; the large subsets are
the measure 1 sets (complements of measure 0 sets). We say that almost
every language in a complexity class C has a given property if the set of
languages in C that exhibit the property has measure 1 in C.
All work to date on the measure-theoretic structure of complexity classes
has employed the resource-bounded measure that is described briefly and
intuitively above. This resource-bounded measure is based on the uniform
probability measure, corresponding to the fact that the coin tosses are fair
and independent in the above-described random experiment. The uniform
probability measure has been a natural and fruitful starting point for the
investigation of resource-bounded measure (just as it was for the investigation
of classical measure), but there are good reasons to also investigate
resource bounded measures that are based on other probability measures.
For example, the study of such alternative resource-bounded measures may
be expected to have the following benefits.
(i) The study will enable us to determine which results of resource-bounded
measure are particular to the uniform probability measure and which
are not. This, in turn, will provide some criteria for identifying contexts
in which the uniform probability measure is, or is not, the natural
choice.
(ii) The study is likely to help us understand how the complexity of the
underlying probability measure interacts with other complexity pa-
rameters, especially in such areas as algorithmic information theory,
average case complexity, cryptography, and computational learning,
where the variety of probability measures already plays a major role.
(iii) The study will provide new tools for proving results concerning resource-bounded
measure based on the uniform probability measure.
The present paper initiates the study of resource-bounded measures that
are based on nonuniform probability measures.
Let C be the set of all languages A ' f0; 1g   . (The set C is often
called Cantor space.) Given a probability measure - on C (a term defined
precisely below), section 3 of this paper describes the basic ideas of resource-bounded
-measure, generalizing definitions and results from [12, 14, 13] to
- in a natural way. In particular, section 3 specifies what it means for a
set X ' C to have p-measure 0 (written -
measure 0 in E (written -(X
or -measure 1 in E 2 .
Most of the results in the present paper concern a restricted (but broad)
class of probability measures on C, namely, coin-toss probability measures
that are given by P-computable, strongly positive sequences of biases. These
probability measures are described intuitively in the following paragraphs
(and precisely in section 3).
Given a sequence ~
the coin-toss probability measure (also call the product probability measure)
given by ~
fi is the probability measure - ~
on C that corresponds to the
random experiment in which a language A 2 C is chosen probabilistically
as follows. For each string s i in the standard enumeration s
f0; 1g   , we toss a special coin, whose probability is fi i of coming up heads,
in which case s i 2 A, and 1 \Gamma fi i of coming up tails, in which case s i 62 A.
The coin tosses are independent of one another.
In the special case where ~ the biases in the sequence
~
fi are all fi, we write - fi for - ~
fi . In particular, - 1
2 is the uniform probability
measure, which, in the literature of resource-bounded measure, is denoted
simply by -.
A sequence ~ of biases is strongly positive if there is
a real number ffi ? 0 such that each fi i 2 ffi]. The sequence ~
fi is P-
computable (and we call it a P-sequences of biases) if there is a polynomial-time
algorithm that, on input (s rational approximation
of fi i to within 2 \Gammar .
In section 4, we prove the Summable Equivalence Theorem, which implies
that, if ~ ff and ~
are strongly positive P-sequences of biases that are
"close" to one another, in the sense that
set
That is, the p-measure based on ~ ff and the p-measure based on ~
fi are in
absolute agreement as to which sets of languages are small.
In general, if ~ ff and ~
fi are not in some sense close to one another, then
the p-measures based on ~ ff and ~
fi need not agree in the above manner. For
example, if ff; fi 2 [0; 1], ff 6= fi, and
\Gamman
then a routine extension of the Weak Stochasticity Theorem of [15] shows
that - ff
Notwithstanding this example, many applications of resource-bounded
measure do not involve arbitrary sets X ' C, but rather are concerned
with the measures of complexity classes and other closely related classes of
languages. Many such classes of interest, including P, NP, co-NP, R, BPP,
AM, P/Poly, PH, PSPACE, etc., are closed under positive, polynomial-time
truth-table reductions (- P
pos\Gammatt -reductions), and their intersections with E
are closed under - P
pos\Gammatt -reductions with linear bounds on the lengths of the
queries
pos\Gammatt -reductions).
The main theorem of this paper is the Bias Equivalence Theorem. This
result, proven in section 8, says that, for every class C of languages that is
closed under - P;lin
pos\Gammatt -reductions, the p-measure of C is somewhat robust with
respect to changes in the underlying probability measure. Specifically, if ~ ff
and ~
are strongly positive P-sequences of biases and C is a class of languages
that is closed under - P;lin
pos\Gammatt -reductions, then the Bias Equivalence Theorem
says that
ff
To put the matter differently, for every strongly positive P-sequence ~
fi of
biases and every class C that is closed under - P;lin
pos\Gammatt -reductions,
This result implies that most applications of resource-bounded measure to
date can be immediately generalized from the uniform probability measure
(in which they were developed) to arbitrary coin-toss probability measures
given by strongly positive P-sequences of biases.
The Bias Equivalence Theorem also offers the following new technique
for proving resource-bounded measure results. If C is a class that is closed
under - P;lin
pos\Gammatt -reductions, then in order to prove that - p
to prove that -
conveniently chosen strongly positive P-
sequence ~
fi of biases. (The Bias Equivalence Theorem has already been put
to this use in the forthcoming paper [17].)
The plausibility and consequences of the hypothesis - p (NP) 6= 0 are
subjects of recent and ongoing research [18, 15, 7, 16, 11, 3, 17]. The Bias
Equivalence Theorem immediately implies that the following three statements
are equivalent.
(H2) For every strongly positive P-sequence ~
fi of biases, -
There exists a strongly positive P-sequence ~
fi of biases such that
~
The statements (H2) and (H3) are thus new, equivalent formulations of the
hypothesis (H1).
The proof of the Bias Equivalence Theorem uses three main tools. The
first is the Summable Equivalence Theorem, which we have already dis-
cussed. The second is the Martingale Dilation Theorem, which is proven
in section 6. This result concerns martingales (defined in section 3), which
are the betting algorithms on which resource-bounded measure is based.
Roughly speaking, the Martingale Dilation Theorem gives a method of transforming
("dilating") a martingale for one coin-toss probability measure into
a martingale for another, perhaps very different, coin-toss probability mea-
sure, provided that the former measure is obtained from the latter via an
"orderly" truth-table reduction.
The third tool used in the proof of our main theorem is the Positive Bias
Reduction Theorem, which is presented in section 7. If ~
ff and ~
are two
strongly positive sequences of biases that are exactly P-computable (with
no approximation), then the positive bias reduction of ~ ff to ~
fi is a truth-table
reduction (in fact, an orderly - P;lin
pos\Gammatt -reduction) that uses the sequence ~
to "approximately simulate" the sequence ~ ff. It is especially crucial for
our main result that this reduction is efficient and positive. (The circuits
constructed by the truth-table reduction contain AND gates and OR gates,
but no NOT gates.)
The Summable Equivalence Theorem, the Martingale Dilation Theorem,
and the Positive Bias Reduction Theorem are only developed and used here
as tools to prove our main result. Nevertheless, these three results are of
independent interest, and are likely to be useful in future investigations.
Preliminaries
In this paper, N denotes the set of all nonnegative integers, Zdenotes the
set of all integers, Z + denotes the set of all positive integers, Q denotes the
set of all rational numbers, and R denotes the set of all real numbers.
We write f0; 1g   for the set of all (finite, binary) strings, and we write
jxj for the length of a string x. The empty string, -, is the unique string of
length 0. The standard enumeration of f0; 1g   is the sequence s
first by length and then lexicographically. For
precedes y in this standard enumeration.
For denotes the set of all strings of length n, and f0; 1g -n
denotes the set of all strings of length at most n.
If x is a string or an (infinite, binary) sequence, and if
then x[i::j] is the string consisting of the i th through j th bits of x. In
is the i-bit prefix of x. We write x[i] for x[i::i], the i th
bit of x. (Note that the leftmost bit of x is x[0], the 0 th bit of x.)
If w is a string and x is a string or sequence, then we write w v x if w
is a prefix of x, i.e., if there is a string or sequence y such that
The Boolean value of a condition OE is
In this paper we use both the binary logarithm log and the
natural logarithm
Many of the functions in this paper are real-valued functions on discrete
domains. These typically have the form
we interpret this to mean that f : f0; 1g   \Gamma! R.)
Such a function f is defined to be p-computable if there is a function
with the following two properties.
(i) For all
(ii) There is an algorithm that, on input computes the
value -
Similarly, f is defined to be p 2 -computable if there is a function -
f as in (2.2)
that satisfies condition (i) above and the following condition.
There is an algorithm that, on input computes the
value -
time.
In this paper, functions of the form (2.1) always have the form
or the form
If such a function is p-computable or p 2 -computable, then we assume without
loss of generality that the approximating function -
f of (2.2) actually has
the form
or the form
respectively.
3 Resource-Bounded -Measure
In this section, we develop basic elements of resource-bounded measure based
on an arbitrary (Borel) probability measure -. The ideas here generalize the
corresponding ideas of "ordinary" resource-bounded measure (based on the
uniform probability measure -) in a straightforward and natural way, so
our presentation is relatively brief. The reader is referred to [12, 13] for
additional discussion.
We work in the Cantor space C, consisting of all languages A ' f0; 1g   .
We identify each language A with its characteristic sequence, which is the
infinite binary sequence -A defined by
-A
for each n 2 N. Relying on this identification, we also consider C to be the
set of all infinite binary sequences.
For each string w 2 f0; 1g   , the cylinder generated by w is the set
Note that C
We first review the well-known notion of a (Borel) probability measure
on C.
probability measure on C is a function
such that
Intuitively, -(w) is the probability that A 2 Cw when we "choose a
language A 2 C according to the probability measure -." We sometimes
Examples.
1. The uniform probability measure - is defined by
for all w 2 f0; 1g   .
2. A sequence of biases is a sequence ~
Given a sequence of biases ~ fi, the ~ fi-coin-toss probability
measure (also called the ~ fi-product probability measure) is the probability
measure - ~
fi defined by
for all w 2 f0; 1g   .
3. If
fi . In this case, we
have the simpler formula
where #(b; w) denotes the number of b's in w. Note that - 1
Intuitively, - ~ fi (w) is the probability that w v A when the language
A ' f0; 1g   is chosen probabilistically according to the following random
experiment. For each string s i in the standard enumeration s
of f0; 1g   , we (independently of all other strings) toss a special coin, whose
probability is fi i of coming up heads, in which case s i 2 A, and 1 \Gamma fi i of
coming up tails, in which case s i 62 A.
Definition. A probability measure - on C is positive if, for all w 2 f0; 1g   ,
If - is a positive probability measure and u; v 2 f0; 1g   , then
the conditional -measure of u given v is
Note that -(ujv) is the conditional probability that A 2 C u , given that
chosen according to the probability measure -.
Most of this paper concerns the following special type of probability
measure.
Definition. A probability measure - on C is strongly positive if (- is positive
and) there is a constant ffi ? 0 such that, for all w 2 f0; 1g   and b 2 f0; 1g,
A sequence of biases ~
strongly positive if
there is a constant
If ~ fi is a sequence of biases, then the following two observations are clear.
1. - ~
fi is positive if and only if fi
2. If - ~ fi is positive, then for each w 2 f0; 1g   ,
and
It follows immediately from these two things that the probability measure
- ~ fi is strongly positive if and only if the sequence of biases ~ fi is strongly
positive.
In this paper, we are primarily interested in strongly positive probability
measures - that are p-computable in the sense defined in section 2.
We next review the well-known notion of a martingale over a probability
measure -. Computable martingales were used by Schnorr [23, 24, 25, 26]
in his investigations of randomness, and have more recently been used by
Lutz [12] in the development of resource-bounded measure.
Let - be a probability measure on C. Then a -martingale is a
If ~
fi is a sequence of biases, then a - ~
fi -martingale is simply called a ~
fi-
martingale. A -martingale is even more simply called a martingale. (That
is, when the probability measure is not specified, it is assumed to be the
uniform probability measure -.)
Intuitively, a -martingale d is a "strategy for betting" on the successive
bits of (the characteristic sequence of) a language A 2 C. The real number
-) is regarded as the amount of money that the strategy starts with. The
real number -(w) is the amount of money that the strategy has after betting
on a prefix w of -A . The identity (3.1) ensures that the betting is "fair"
in the sense that, if A is chosen according to the probability measure -,
then the expected amount of money is constant as the betting proceeds.
(See [23, 24, 25, 26, 27, 12, 14, 13] for further discussion.) Of course, the
"objective" of a strategy is to win a lot of money.
Definition. A -martingale d succeeds on a language A 2 C if
lim sup
The success set of a -martingale d is the set
succeeds on Ag :
We are especially interested in martingales that are computable within
some resource bound. (Recall that the p-computability and p 2 -computability
of real valued functions were defined in section 2.)
Let - be a probability measure on C.
1. A p-martingale is a -martingale that is p-computable.
2. A p 2 -martingale is a -martingale that is p 2 -computable.
A p- ~
fi -martingale is called a p- ~
fi-martingale, a p-martingale is called
a p-martingale, and similarly for p 2 .
We now come to the fundamental ideas of resource-bounded -measure.
Let - be a probability measure on C, and let X ' C.
1. X has p-measure 0, and we write - there is a p-
martingale d such that X ' S 1 [d].
2. X has p-measure 1, and we write -
The conditions - p 2
are defined analogously.
Let - be a probability measure on C, and let X ' C.
1. X has -measure 0 in E, and we write -(X
2. X has -measure 1 in E, and we write -(X
3. X has -measure 0 in E 2 , and we write -(X
4. X has -measure 1 in E 2 , and we write -(X
Just as in the uniform case [12], the resource bounds p and p 2 of the
above definitions are only two possible values of a very general parameter.
Other choices of this parameter yield classical -measure [5], constructive
-measure (as used in algorithmic information theory [29, 27]), -measure in
the set REC, consisting of all decidable languages, -measure in ESPACE,
etc.
The rest of this section is devoted to a very brief presentation of some
of the fundamental theorems of resource-bounded -measure. One of the
main objectives of these results is to justify the intuition that a set with
-measure 0 in E contains only a "negligibly small" part of E (with respect
to -). For the purpose of this paper, it suffices to present these results for p-
-measure and -measure in E. We note, however, that all these results hold
a fortiori for p 2 -measure, rec-measure, classical -measure, -measure
in -measure in ESPACE, etc.
We first note that -measure 0 sets exhibit the set-theoretic behavior of
small sets.
1. X is a p-union of the p-measure 0 sets
and there is a sequence d -martingales with the following
two properties.
(i) For each k 2 N, X k ' S 1 [d k ].
(ii) The function (k; w) 7! d k (w) is p-computable.
2. X is a p-union of the sets X
and there is a sequence d 0 ; d 1
with the following two properties.
(i) For each k 2 N,
(ii) The function (k; w) 7! d k (w) is p-computable.
Lemma 3.1. Let - be a probability measure on C, and let I be either the
collection of all p-measure 0 subsets of C, or the collection of all subsets
of C that have -measure 0 in E. Then I has the following three closure
properties.
1. If X ' Y 2 I, then X 2 I.
2. If X is a finite union of elements of I, then X 2 I
3. If X is a p-union of elements of I, then X 2 I.
Proof (sketch). Assume that X is a p-union of the p-measure 0 sets
be as in the definition of this condition.
Without loss of generality, assume that d k (-) ? 0 for each k 2 N. It suffices
to show that - remaining parts of the lemma are obvious or
follow directly from this.) Define
Its is easily checked that d is a p-martingale and that X ' S 1 [d], so
We next note that, if - is strongly positive and p-computable, then every
singleton subset of E has p-measure 0.
Lemma 3.2. If - is a strongly positive, p-computable probability measure
on C, then for every A 2 E,
Proof (sketch). Assume the hypothesis, and fix ffi ? 0 such that, for all
It is easily checked that d is a p-martingale and that, for all n 2 N,
\Gamman , whence A 2 S 1 [d].  .
Note that, for A 2 E, the "point-mass" probability measure
-A
is p-computable, and fAg does not have p- A -measure 0. Thus, the strong
positivity hypothesis cannot be removed from Lemma 3.2.
We now come to the most crucial issue in the development of resource-bounded
measure. If a set X has -measure 0 in E, then we want to say
that X contains only a "negligible small" part of E. In particular, then, it
is critical that E itself not have -measure 0 in E. The following theorem
establishes this and more.
Theorem 3.3. Let - be a probability measure on C, and let w 2 f0; 1g   .
If -(w) ? 0, then Cw does not have -measure 0 in E.
Proof (sketch). Assume the hypothesis, and let d be a p-martingale. It
suffices to show that
Since d is p-computable, there is a function -
with the following two properties.
(i) For all r 2 N and w 2 f0; 1g   , j -
(ii) There is an algorithm that computes -
w) in time polynomial in
Define a language A recursively as follows. First, for
w[i]. Next assume that the string x
With the language A so defined, it is easy to check that A 2 Cw " E. It
is also routine to check that, for all i - jwj,
It follows inductively that, for all n - jwj,
This implies that
lim sup
whence A 62 S 1 [d].
As in the case of the uniform probability measure [12], more quantitative
results on resource-bounded -measure can be obtained by considering the
unitary success set
Cw
and the initial value d(-) of a p-martingale d. For example, generalizing
the arguments in [12] in a straightforward manner, this approach yields a
Measure Conservation Theorem for -measure (a quantitative extension of
Theorem 3.3 ) and a uniform, resource-bounded extension of the classical
first Borel-Cantelli lemma. As these results are not used in the present
paper, we refrain from elaborating here.
4 Summable Equivalence
If two probability measures on C are sufficiently "close" to one another, then
the Summable Equivalence Theorem says that the two probability measures
are in absolute agreement as to which sets of languages have p-measure 0
and which do not. In this section, we define this notion of "close" and prove
this result.
Let - be a positive probability measure on C, let A ' f0; 1g   ,
and let i 2 N. Then the i th conditional -probability along A is
Two positive probability measures - and - 0 on C are summably
equivalent, and we write - t - 0 , if for every A ' f0; 1g   ,X
It is clear that summable equivalence is an equivalence relation on the
collection of all positive probability measures on C. The following fact is
also easily verified.
Lemma 4.1. Let - and - 0 be positive probability measures on C. If - t - 0 ,
then - is strongly positive if and only if - 0 is strongly positive.
The following definition gives the most obvious way to transform a martingale
for one probability measure into a martingale for another.
probability measures on C with - 0 positive,
and let d be a -martingale. Then the canonical adjustment of d to - 0 is the
defined by
for all w 2 f0; 1g   .
It is trivial to check that the above function d 0 is indeed a - 0 -martingale.
The following lemma shows that, for strongly positive probability measures,
summable equivalence is a sufficient condition for d 0 to succeed whenever d
succeeds.
Lemma 4.2. Let - and - 0 be strongly positive probability measures on C,
let d be a -martingale, and let d 0 be the canonical adjustment of d to - 0 . If
Proof. Assume the hypothesis, and let A 2 S 1 [d]. For each i 2 N, let
The hypothesis - t - 0 says that
In particular, this implies
that - i \Gamma! 0 as i \Gamma! 1, so we have the Taylor approximation
as i \Gamma! 1. Thus j
j is asymptotically equivalent to
as i \Gamma! 1.
strongly positive, it follows that
1. Thus, if we
there is a positive constant c such that, for all
whence
Since A 2 S 1 [d], we thus have
lim sup
so A 2 S 1 [d 0 ].
The following useful result is now easily established.
Theorem 4.3 (Summable Equivalence Theorem). If - and - 0 are strongly
positive, p-computable probability measures on C such that - t - 0 , then
for every set X ' C,
Proof. Assume the hypothesis, and assume that -
it suffices to show that - 0
there is a p-computable
-martingale d such that X ' S 1 [d]. Let d 0 be the canonical adjustment of
d to - 0 . Since d; -; and - 0 are all p-computable, it is easy to see that d 0 is
p-computable. us that
5 Exact Computation
It is sometimes useful or convenient to work with probability measures that
are rational-valued and efficiently computable in an exact sense, with no
approximation. This section presents two very easy results identifying situations
in which such probability measures are available.
Definition. A probability measure - on C is exactly p-computable if
and there is an algorithm that computes -(w) in time
polynomial in jwj.
Lemma 5.1. For every strongly positive, p-computable probability measure
on C, there is an exactly p-computable probability measure - 0 on C such
that - t - 0 .
Proof. Let - be a p-computable probability measure on C, and fix a function
that testifies to the p-computability of -. Since
- is strongly positive, there is a constant c 2 N such that, for all w 2 f0; 1g   ,
Fix such a c and, for all w 2 f0; 1g   , define
ae
oe
It is clear that - 0 is an exactly p-computable probability measure on C.
Now let w 2 f0; 1g   and b 2 f0; 1g. For convenience, let
Note that
It is clear by inspection that - 0 (wbjw) can be written in the form
where
We thus have
whence
a 1
a 2
a 2 a 0- 2fflffi \Gamma2
For all A ' f0; 1g   , then, we haveX
For some purposes (including those of this paper), the requirement of
p-computability is too weak, because it allows -(w) to be computed (or
approximated) in time polynomial in jwj, which is exponential in the length
of the last string decided by w when we regard w as a prefix of a language A.
In such situations, the following sort of requirement is often more useful. (We
only give the definitions for sequences of biases, i.e., coin-toss probability
measures, because this suffices for our purposes in this paper. It is clearly a
routine matter to generalize further.)
1. A P-sequence of biases is a sequence ~
for which there is a function
with the following two properties.
(i) For all
(ii) There is an algorithm that, for all
fi(i; r) in
time polynomial in js i j +r (i.e., in time polynomial in log(i+1)+
r).
2. A P-exact sequence of biases is a sequence ~
such that the function i 7\Gamma! fi i is computable
in time polynomial in js i j.
Definition. If ~ ff and ~ fi are sequences of biases, then ~
ff and ~
are summably
equivalent, and we write ~ ff t ~ fi, if
It is clear that ~ ff t ~
fi if and only if - ~ ff t - ~
fi .
Lemma 5.2. For every P-sequence of biases ~
fi, there is a P-exact sequence
of biases ~
fi 0 such that ~
Proof. Let ~ fi be a strongly positive P-sequence of biases, and let -
be a function that testifies to this fact. For each i 2 N, let
and let ~
fi 0 is a P-exact sequence of biases, andX
so ~ fi t ~
6 Martingale Dilation
In this section we show that certain truth-table reductions can be used to
dilate martingales for one probability measure into martingales for another,
perhaps dissimilar, probability measure on C. We first present some terminology
and notation on truth-table reductions. (Most of this notation is
standard [22], but some is specialized to our purposes.)
A truth-table reduction (briefly, a - tt -reduction) is an ordered pair (f; g)
of total recursive functions such that for each x 2 f0; 1g   , there exists n(x) 2
such that the following two conditions hold.
(i) f(x) is (the standard encoding of) an n(x)-tuple (f 1
of strings f i (x) 2 f0; 1g   , which are called the queries of the reduction
(f; g) on input x. We use the notation Q (f;g)
for the set of such queries.
(ii) g(x) is (the standard encoding of) an n(x)-input, 1-output Boolean
circuit, called the truth table of the reduction (f; g) on input x. We
identify g(x) with the Boolean function computed by this circuit, i.e.,
A truth-table reduction (f; g) induces the function
If A and B are languages and (f; g) is a - tt -reduction, then (f; g) reduces
B to A, and we write
(A). More generally, if A and B are languages, then B is truth-table
reducible (briefly, - tt -reducible) to A, and we write B - tt A, if there
exists a - tt -reduction (f; g) such that B - tt A via (f; g).
If (f; g) is a - tt -reduction, then the function F (f;g) : C \Gamma! C defined
above induces a corresponding function
defined as follows. (It is standard practice to use the same notation for
these two functions, and no confusion will result from this practice here.)
Intuitively, if A 2 C and w v A, then F (f;g) (w) is the largest prefix of
(A) such that w answers all queries in this prefix. Formally, let w 2
If Q (f;g) (x) ' fs
Otherwise,
where m is the greatest nonnegative integer such that
Now let (f; g) be a - tt -reduction, and let z 2 f0; 1g   . Then the inverse
image of the cylinder C z under the reduction (f; g) is
We can write this set in the form
w2I
where I is the set of all strings w 2 f0; 1g   with the following properties.
(i) z v F (f;g) (w).
(ii) If w 0 is a proper prefix of w, then z 6v F (f;g) (w 0 ).
Moreover, the cylinders Cw in this union are disjoint, so if - is a probability
measure on C, then
w2I
The following well-known fact is easily verified.
Lemma 6.1. If - is a probability measure on C and (f; g) is a - tt -reduction,
then the function
is also a probability measure on C.
The probability measure - (f;g) of Lemma 6.1 is called the probability
measure induced by - and (f; g).
In this paper, we only use the following special type of - tt -reduction.
-reduction (f; g) is orderly if, for all x;
y, v. That is, if x precedes y
(in the standard ordering of f0; 1g   ), then every query of (f; g) on input x
precedes every query of (f; g) on input y.
The following is an obvious property of orderly - tt -reductions.
Lemma 6.2. If - is a coin-toss probability measure on C and (f; g) is an
orderly - tt -reduction, then - (f;g) is also a coin-toss probability measure on
C.
Note that, if (f; g) is an orderly - tt -reduction, then F (f;g) (w) 2 f0; 1g
for all w 2 f0; 1g   . Note also that the length of F (f;g) (w) depends only
upon the length of w (i.e., implies that jF (f;g)
Finally, note that for each m 2 N there exists l 2 N such that jF (f;g) (0 l
m.
Definition. Let (f; g) be an orderly - tt -reduction.
1. An (f; g)-step is a positive integer l such that F (f;g) (0
2. For k 2 N, we let step(k) be the least (f; g)-step l such that l - k.
The following construction is crucial to the proof of our main theorem.
Let - be a positive probability measure on C, let (f; g) be an
orderly - tt -reduction, and let d be a - (f;g) -martingale. Then the (f; g)-
dilation of d is the function
u2f0;1g l\Gammak
In other words, (f; g)bd(w) is the conditional -expected value of d(F (f;g) (w 0 )),
given that w v w 0 and jw step(jwj). We do not include the probability
measure - in the notation (f; g)bd because - (being positive) is implicit in
d.
Intuitively, the function (f; g)bd is a strategy for betting on a language
A, assuming that d itself is a strategy for betting on the language F (f;g) (A).
The following theorem makes this intuition precise.
Theorem 6.3 (Martingale Dilation Theorem). Assume that - is a positive
coin-toss probability measure on C, (f; g) is an orderly - tt -reduction, and d
is a - (f;g) -martingale. Then (f; g)bd is a -martingale. Moreover, for every
language A ' f0; 1g   , if d succeeds on F (f;g) (A), then (f; g)bd succeeds on
A.
A very special case of the above result (for strictly increasing - P
-reductions
under the uniform probability measure) was developed by Ambos-Spies, Ter-
wijn, and Zheng [2], and made explicit by Juedes and Lutz [8]. Our use of
martingale dilation in the present paper is very different from the simple
padding arguments of [2, 8].
The following two technical lemmas are used in the proof of Theorem
6.3.
Lemma 6.4. Assume that - is a positive coin-toss probability measure on
C and (f; g) is an orderly - tt -reduction. Let
and assume that is an (f; g)-step. Let l 1). Then, for
Proof. Assume the hypothesis. Then
since - is a coin-toss probability measure, we have -(w 0 ujw
for each w 0 2 f0; 1g k such that F (w 0 (w). Also, since (f; g) is orderly,
the conditions F (w 0 are equivalent for each

Lemma 6.5. Assume that - is a positive coin-toss probability measure on
C and (f; g) is an orderly - tt -reduction. Let assume that d
is a - (f;g) -martingale. Let w 2 f0; 1g   , assume that is an (f; g)-step,
and let l 1). Then
u2f0;1g l\Gammak
Proof. Assume the hypothesis. Since d is a - (f;g) -martingale and - (f;g)
is positive, we have
It follows by Lemma 6.4 that
u2f0;1g l\Gammak
Proof of Theorem 6.3. Assume the hypothesis, and let
To see that (f; g)bd is a -martingale, let w 2 f0; 1g   , let
1). We have two cases.
Case I.
u2f0;1g
u2f0;1g
u2f0;1g l\Gammak
Case II. is an (f; g)-step, so (f;
whence by Lemma 6.5
u2f0;1g l\Gammak
Calculating as in Case I, it follows that
This completes the proof that (f; g)bd is a -martingale.
To complete the proof, let A ' f0; 1g   , and assume that d succeeds
on F (A). For each n 2 N, let w is the unique
(f; g)-step such that jF(0 l n
so
lim sup
Thus (f; g)bd succeeds on A.
7 Positive Bias Reduction
In this section, we define and analyze a positive truth-table reduction that
encodes an efficient, approximate simulation of one sequence of biases by
another.
Intuitively, if ~
ff and ~
are strongly positive sequences of biases, then
the positive bias reduction of ~ ff to ~
fi is a - tt -reduction (f; g) that "tries
to simulate" the sequence ~ ff with the sequence ~
fi by causing - ~ ff to be the
probability distribution induced by - ~ fi and (f; g). In general, this objective
will only be approximately achieved, in the sense that the probability distribution
induced by - ~
fi and (f; g) will actually be a probability distribution
, where ~ ff 0 is a sequence of biases such that ~ ff 0 t ~ ff. This situation is
depicted schematically in Figure 1, where the broken arrow indicates that
(f; g) "tries" to reduce ~ ff to ~
fi, while the solid arrow indicates that (f; g)
actually reduces ~ ff 0 to ~ fi.

Figure

1: Schematic depiction of positive bias reduction
The reduction (f; g) is constructed precisely as follows.
Construction 7.1 (Positive Bias Reduction). Let ~ ff and ~
fi be strongly
positive sequences of biases. Let
e:
For each x 2 f0; 1g   and 0 - xy, where y is the
th element of f0; 1g cjxj , and let j(x; n) be the index of the string q(x; n),
begin
while ff 0
do
begin
l := 0;
while ff 0
do
begin
l
end .

Figure

2: Construction of positive bias reduction
n). Then the positive bias reduction of ~
ff to ~
fi is the
ordered pair (f; g) of functions defined by the procedure in Figure 2. (For
convenience, the procedure defines additional parameters that are useful in
the subsequent analysis.)
The following general remarks will be helpful in understanding Construction
7.1.
(a) The boldface variables v 0 Boolean inputs to the Boolean
function g(x) being constructed. The Boolean function g(x) is an OR
of k(x) Boolean functions h(x; k), i.e.,
The Boolean functions g(x; are preliminary approximations
of the Boolean function g(x). In particular,
for all 0 - k - k(x). Thus g(x; 0) is the constant-0 Boolean function.
(b) The Boolean function h(x; k) is an AND of l(x; consecutive input
variables. The subscript n is incremented globally so that no input
variable appears more than once in g(x). Just as g(x; k) is the k th
"partial OR" of g(x), h(x; k; l) is the l th "partial AND" of h(x; k).
Thus h(x; k; 0) is the constant-1 Boolean function.
(c) The input variables v 0 , correspond to the respective queries
then we have
chosen
according to the sequence of biases ~
fi, then fi j(x;n) is the probability
that is the probability that h(x;
i is the
probability that 1. The while-loops ensure that ff
The following lemmas provide some quantitative analysis of the behavior
of Construction 7.1.
Lemma 7.2. In Construction 7.1, for all x 2 f0; 1g   and 0 - k - k(x),
log e
Proof. Fix such x and k, and let l  the result is trivial,
so assume that l   ? 0. Then, by the minimality of l   ,
so
so
It follows that
whence
l

Lemma 7.3. In the Construction 7.1, for all x 2 f0; 1g   , and 0 - k -
Proof. Fix such x and k with
The lemma now follows immediately by induction.
Lemma 7.4. In Construction 7.1, for all x 2 f0; 1g   ,
log e
Proof. Fix x 2 f0; 1g   . By Lemma 7.3 and the minimality of k(x),
so
so
log e

Lemma 7.5. In Construction 7.1, for all x 2 f0; 1g   ,
Proof. Let x 2 f0; 1g   . Then
so by Lemmas 7.2, 7.4, and the bound 1
log e
cjxj
log

Definition. Let (f; g) be a - tt -reduction.
1. (f; g) is positive (briefly, a - pos\Gammatt -reduction) if, for all A; B ' f0; 1g   ,
2. (f; g) is polynomial-time computable (briefly, a - P
tt -reduction) if the
functions f and g are computable in polynomial time.
3. (f; g) is polynomial-time computable with linear-bounded queries (briefly,
a - P;lin
tt -reduction and there is a constant
c 2 N such that, for all x 2 f0; 1g   , Q (f;g) (x) ' f0; 1g -c(1+jxj) .
Of course, a - P;lin
pos\Gammatt -reduction is a - tt -reduction with all the above properties

The following result presents the properties of the positive bias reduction
that are used in the proof of our main theorem.
Theorem 7.6 (Positive Bias Reduction Theorem). Let ~ ff and ~
fi be strongly
positive, P-exact sequences of biases, and let (f; g) be the positive bias reduction
of ~ ff to ~
fi. Then (f; g) is an orderly - P;lin
pos\Gammatt -reduction, and the
probability measure induced by - ~
fi and (f; g) is a coin-toss probability measure
Proof. Assume the hypothesis. By inspection and Lemma 7.5, the pair
(f; g) is an orderly - P;lin
pos\Gammatt -reduction. (Lemma 7.5 also ensures that f(x) is
well-defined.) The reduction is also positive, since only AND's and OR's are
used in the construction of g(x). Thus (f; g) is an orderly - P;lin
pos\Gammatt -reduction.
By remark (c) following Construction 7.1, the probability measure induced
by - ~ fi and (f; g) is the coin-toss probability measure - ~
, where
~
defined in the construction. Moreover,X
so ~ ff t ~
8 Equivalence for Complexity Classes
Many important complexity classes, including P, NP, co-NP, R, BPP, AM,
P/Poly, PH, PSPACE, etc., are known to be closed under - P
pos\Gammatt -reductions,
hence certainly under - P;lin
pos\Gammatt -reductions. The following theorem, which is
the main result of this paper, says that the p-measure of such a class is somewhat
insensitive to certain changes in the underlying probability measure.
The proof is now easy, given the machinery of the preceding sections.
Theorem 8.1 (Bias Equivalence Theorem). Assume that ~ ff and ~
are
strongly positive P-sequences of biases, and let C be a class of languages
that is closed under - P;lin
pos\Gammatt -reductions. Then
ff
Proof. Assume the hypothesis, and assume that - ~ ff
it suffices to show that - ~ fi
The proof follows the scheme depicted in Figure 3. By Lemma 5.2,
there exist P-exact sequences ~
ff 0 and ~
fi 0 such that ~ ff t ~
ff 0 and ~ fi t ~
(f; g) be the positive bias reduction of ~
ff 0 to ~
Then, by the Positive Bias
Reduction Theorem (Theorem 7.6), (f; g) is an orderly - P;lin
pos\Gammatt -reduction,
and the probability measure induced by - ~
fi and (f; g) is - ~

Figure

3: Scheme of proof of Bias Equivalence Theorem
ff 00 and - ~ ff
the Summable Equivalence Theorem
(Theorem 4.3) tells us that there is a p-~ff 00 -martingale d such that C ' S 1 [d].
By the Martingale Dilation Theorem (Theorem 6.3), the function (f; g)bd
is then a ~
In fact, it easily checked that (f; g)bd is a p- ~ fi 0 -
martingale.
Now let A 2 C. Then, since C is closed under - P;lin
pos\Gammatt -reductions,
It follows by the Martingale Dilation Theorem
that A 2 S 1 [(f; g)bd]. Thus C ' S 1 [(f; g)bd]. Since (f; g)bd is a p- ~ fi 0 -
martingale, this shows that -
Finally, since ~
the Summable Equivalence Theorem that -

It is clear that the Bias Equivalence Theorem remains true if the resource
bound on the measure is relaxed. That is, the analogs of Theorem 8.1 for
measure, pspace-measure, rec-measure, constructive measure, and classical
measure all immediately follow. We conclude by noting that the analogs of
Theorem 8.1 for measure in E and measure in E 2 also immediately follow.
Corollary 8.2. Under the hypothesis of Theorem 8.1,
and
Proof. If C is closed under - P;lin
pos\Gammatt -reductions, then so are the classes
and
9 Conclusion
Our main result, the Bias Equivalence Theorem, says that every strongly
positive, P-computable, coin-toss probability measure - is equivalent to the
uniform probability measure -, in the sense that
for all classes C 2 \Gamma, where \Gamma is a family that contains P, NP, co-NP, R, BPP,
P/Poly, PH and many other classes of interest. It would be illuminating to
learn more about which probability measures are, and which probability
measures are not, equivalent to - in this sense.
It would also be of interest to know whether the Summable Equivalence
Theorem can be strengthened. Specifically, say that two sequences of biases
~ ff and ~ fi are square-summably equivalent, and write ~ ff t 2 ~
fi, if
classical theorem of Kakutani [9] says that, if ~ ff and ~
are
strongly positive sequences of biases such that ~ ff t 2 ~ fi, then for every set
has (classical) ~ ff-measure 0 if and only if X has ~
fi-measure 0. A
constructive improvement of this theorem by Vovk [28] says that, if ~ ff and
~
are strongly positive, computable sequences of biases such that ~ ff t 2 ~
fi,
then for every set X ' C, X has constructive ~ ff-measure 0 if and only if
X has constructive ~
fi-measure 0. (The Kakutani and Vovk theorems are
more general than this, but for the sake of brevity, we restrict the present
discussion to coin-toss probability measures.) The Summable Equivalence
Theorem is stronger than these results in one sense, but weaker in another.
It is stronger in that it holds for p-measure, but it is weaker in that it
requires the stronger hypothesis that ~ ff t ~ fi. We thus ask whether there is
a "square-summable equivalence theorem" for p-measure. That is, if ~ ff and
~
are strongly positive, p-computable sequences of biases such that ~ ff t 2 ~
fi,
is it necessarily the case that, for every set X ' C, X has p-~ff-measure 0
if and only if X has p- ~
fi-measure 0? (Note: Kautz [10] has very recently
answered this question affirmatively.)

Acknowledgments

. We thank Giora Slutzki, Martin Strauss, and
other participants in the ISU Information and Complexity Seminar for useful
remarks and suggestions. We especially thank Giora Slutzki for suggesting
a simplified presentation of Lemma 4.2.



--R

A comparison of weak completeness notions.
Resource bounded randomness and weakly complete problems.
Fine separation of average time complexity classes.
Families of recursive predicates of measure zero.
Measure Theory.
Weakly complete problems are not rare.
The complexity and distribution of hard problems.
Weak completeness in E and
On the equivalence of infinite product measures.
Personal communication
Observations on measure and lowness for
Almost everywhere high nonuniform complexity.
The quantitative structure of exponential time.
Weakly hard problems.

Cook versus Karp-Levin: Separating completeness notions if NP is not small

Almost every set in exponential time is P-bi-immune
"almost all"

Pseudorandom generators

Klassifikation der Zufallsgesetze nach Komplexit-at und Ordnung
A unified approach to the definition of random sequences.

Process complexity and effective random tests.
Random Sequences.
On a randomness criterion.
The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms.
--TR
complexity classes;martingales;resource-bounded measure