A Generalization of Resource-Bounded Measure, with Application to the BPP vs. EXP Problem.
We introduce  resource-bounded betting games and propose a generalization of Lutz's resource-bounded measure in which the choice of the next string to bet on is fully adaptive. Lutz's martingales are equivalent to betting games constrained to bet on strings in lexicographic order. We show that if strong pseudorandom number generators exist, then betting games are equivalent to martingales for measure on E and EXP. However, we construct betting games that succeed on certain classes whose Lutz measures are important open problems: the class of polynomial-time Turing-complete languages in EXP and its superclass of polynomial-time Turing-autoreducible languages. If an EXP-martingale succeeds on either of these classes, or if betting games have the "finite union property" possessed by Lutz's measure, one obtains the nonrelativizable consequence $\mbox{BPP} \neq \mbox{EXP}$. We also show that if $\mbox{EXP} \neq \mbox{MA}$, then the polynomial-time truth-table-autoreducible languages have Lutz measure zero, whereas if
Introduction
Lutz's theory of measure on complexity classes is now usually defined in terms of resource-bounded
martingales. A martingale can be regarded as a gambling game played on unseen languages A. Let
be the standard lexicographic ordering of strings. The gambler G starts with capital
places a bet
A." Given a fixed particular
language A, the bet's outcome depends only on whether s 1 2 A. If the bet wins, then the new
capital while if the bet loses, C . The gambler then places a bet
on (or against) membership of the string s 2 , then on s 3 , and so forth. The gambler
succeeds if G's capital C i grows toward +1. The class C of languages A on which G succeeds
(and any subclass) is said to have measure zero. One also says G covers C. Lutz and others (see
[Lut97]) have developed a rich and extensive theory around this measure-zero notion, and have
shown interesting connections to many other important problems in complexity theory.
We propose the generalization obtained by lifting the requirement that G must bet on strings
in lexicographic order. That is, G may begin by choosing any string x 1 on which to place its first
bet, and after the oracle tells the result, may choose any other string x 2 for its second bet, and so
forth. Note that the sequences x may be radically different
for different oracle languages A-in complexity-theory parlance, G's queries are adaptive. The lone
restriction is that G may not query (or bet on) the same string twice. We call G a betting game.
Our betting games remedy a possible lack in the martingale theory, one best explained in
the context of languages that are "random" for classes D such as E or EXP. A language L is
D-random if L cannot be covered by a D-martingale. Based on one's intuition about random 0-1
sequences, the language L should likewise be D-random, where flip(x) changes
every 0 in x to a 1 and vice-versa. However, this closure property is not known for E-random or
EXP-random languages, because of the way martingales are tied to the fixed lex ordering of \Sigma   .
Betting games can adapt to easy permutations of \Sigma   such as that induced by flip. Similarly, a class
C that is small in the sense of being covered by a (D-) betting game remains small if the languages
are so permuted. In the r.e./recursive theory of random languages, our generalization is
similar to "Kolmogorov-Loveland place-selection rules" (see [Lov69]). We make this theory work
for complexity classes via a novel definition of "running in time t(n)" for an infinite process.
Our new angle on measure theory may be useful for attacking the problem of separating BPP
from EXP, which has recently gained prominence in [IW98]. In Lutz's theory it is open whether the
class of EXP-complete sets-under polynomial-time Turing reductions-has EXP-measure zero. If
so (in fact if this set does not have measure one), then by results of Allender and Strauss [AS94],
BPP 6= EXP. Since there are oracles A such that BPP A = EXP A [Hel86], this kind of absolute
separation would be a major breakthrough. We show that the EXP-complete sets can be covered
by an EXP betting game-in fact, by an E-betting game. The one technical lack in our theory as
a notion of measure is also interesting here: If the "finite unions" property holds for betting games
(viz. martingales do
enjoy the permutation-invariance of betting games, then BPP 6= EXP. Finally, we show that if a
pseudorandom number generator (PRG) of security 2
n\Omega\Gamma/1 exists, then for every EXP-betting game
G one can find an EXP-martingale that succeeds on all sets covered by G. PRGs of higher security\Omega\Gamma n) likewise imply the equivalence of E-betting games and E-measure. Ambos-Spies and Lempp
[ASL96] proved that the EXP-complete sets have E-measure zero under a different hypothesis,
namely
Measure theory and betting games help us to dig further into questions about PRGs and
complexity-class separations. Our tool is the notion of an autoreducible set, whose importance in
complexity theory was argued by Buhrman, Fortnow, van Melkebeek, and Torenvliet [BFvMT98]
(after [BFT95]). A language L is - p
-autoreducible if there is a polynomial-time oracle TM Q such
that for all inputs x, Q L correctly decides whether x 2 L without ever submitting x itself as a
query to L. If Q is non-adaptive (i.e., computes a polynomial-time truth-table reduction), we say
L is - p
tt -autoreducible. We show that the class of - p
T -autoreducible sets is covered by an E-betting
game. Since every EXP-complete set is - p
-autoreducible [BFvMT98], this implies results given
above. The subclass of - p
tt -autoreducible sets provides the following tighter connection between
measure statements and open problems about EXP:
ffl If the - p
tt -autoreducible sets do not have E-measure zero, then
ffl If the - p
-autoreducible sets do not have E-measure one in EXP, then EXP 6= BPP.
Here MA is the "Merlin-Arthur" class of Babai [Bab85, BM88], which contains BPP and NP.
Since EXP 6= MA is strongly believed, one would expect the class of - p
-autoreducible sets to
have E-measure zero, but proving this-or proving any of the dozen other measure statements in
Corollaries 6.2 and 6.5-would yield a proof of EXP 6= BPP.
In sum, the whole theory of resource-bounded measure has progressed far enough to wind the
issues of (pseudo-)randomness and stochasticity within exponential time very tightly. We turn the
wheels a few more notches, and seek greater understanding of complexity classes in the places where
the boundary between "measure one" and "measure zero" seems tightest.
Section 2 reviews the formal definitions of Lutz's measure and martingales. Section 3 introduces
betting games, and shows that they are a generalization of martingales. Section 4 shows how to
simulate a betting game by a martingale of perhaps-unavoidably higher time complexity. Section 5,
however, demonstrates that strong PRGs (if there are any) allow one to compute the martingale
in the same order of time. Section 6 presents our main results pertaining to autoreducible sets,
including our main motivating example of a concrete betting game. The concluding Section 7
summarizes open problems and gives prospects for future research.
A preliminary version of this paper without proofs appeared in the proceedings of STACS'98,
under the title "A Generalization of Resource-Bounded Measure, With an Application."
Martingales
A martingale is abstractly defined as a function d from f 0; 1 g   into the nonnegative reals that
satisfies the following "average law": for all w
The interpretation in Lutz's theory is that a string w 2 f 0; 1 g   stands for an initial segment of
a language over an arbitrary alphabet \Sigma as follows: Let s be the standard lexicographic
ordering of \Sigma   . Then for any language A ' \Sigma   , write w v A if for all iff the
ith bit of w is a 1. We also regard w as a function with domain and range
writing w(s i ) for the ith bit of w. A martingale d succeeds on a language A if the sequence
of values d(w) for w v A is unbounded. If J is a set of strings such that for any w 2 f 0; 1 g   and
any b 2 f 0; 1 g, d(wb) 6= d(w) implies s jwbj 2 J , we say that the martingale d is active only on J .
stand for the (possibly empty, often uncountable) class of languages on which d
succeeds.
Definition 2.1 (cf. [Lut92, May94]). Let \Delta be a complexity class of functions. A class C of
languages has \Delta-measure zero, written - \Delta there is a martingale d computable in \Delta such
that C ' S 1 [d]. One also says that d covers C.
Lutz defined complexity bounds in terms of the length of the argument w to d, which we
denote by N . However, we also work in terms of the largest length n of a string in the domain of
w. For N ? 0, n equals blog Nc; all we care about is that Because
complexity bounds on languages we want to analyze will naturally be stated in terms of n, we
prefer to use n for martingale complexity bounds. The following correspondence is helpful:
- measure on EXP
Our convention lets us simply write "- E " for E-measure (regarding \Delta as E for functions),
similarly "- EXP " for EXP-measure, and generally - \Delta for any \Delta that names both a language and
function class. Abusing notation similarly, we define:
Definition 2.2 ([Lut92]). A class C has \Delta-measure one, written - \Delta
The concept of resource bounded measure is known to be robust under several changes [May94].
The following lemma has appeared in various forms [May94, BL96]. It essentially says that we can
assume a martingale grows almost monotonically (sure winnings) and not too fast (slow winnings).
Lemma 2.1 ("Slow-but-Sure-Winnings" lemma for martingales) Let d be a martingale.
Then there is a martingale d 0 with S 1 [d] ' S 1 [d 0 ] such that
If d is computable in time t(n) , then d 0 is computable in time O(2 n t(n)).
The idea is to play the strategy of d, but in a more conservative way. Say we start with an
initial capital of $1. We will deposit a part c of our capital on a bank and only play the strategy
underlying d on the remaining liquid part e of our capital. We start with no savings and a liquid
capital of $1. When our liquid capital e would reach $2 or exceed that level, we deposit an additional
$1 or $2 to our savings account c so as to keep the liquid capital in the range $[1; 2) at all times. If
d succeeds, it will push the liquid capital infinitely often to $2 or above, so c grows to infinity, and
d 0 succeeds too. Since we never take money out of our savings account c, and the liquid capital e is
bounded by $2, once our total capital d reached a certain level, it will never go more
than $2 below that level anymore, no matter how bad the strategy underlying d is. On the other
hand, since we add at most $2 to c in each step, d 0 (w) cannot exceed 2(jwj
We now give the formal proof.
Proof. (of Lemma 2.1) Define d
Checking the time and space complexity bounds for d 0 is again straightforward.
We can show by induction on jwj that
and that
from which it follows that d 0 is a martingale.
If d succeeds on !, e(w) will always remain positive for w v !, and d(wb)
or more infinitely often. Consequently, lim wv!;jwj!1
that S 1 [d] ' S 1 [d 0 ]. Moreover, by (4) and the fact that c does not decrease along any sequence,
we have that
Since c can increase by at most 2 in every step, c(w) - 2jwj. Together with (4), this yields
that
One can also show that S 1 [d 0 ] ' S 1 [d] in Lemma 2.1, so the success set actually remains intact
under the above transformation.
As with Lebesgue measure, the property of having resource-bounded measure zero is monotone
and closed under union ("finite unions property"). A resource-bounded version of closure under
countable unions also holds. The property that becomes crucial in resource-bounded measure is
that the whole space \Delta does not have measure zero, which Lutz calls the "measure conservation"
property. With a slight abuse of meaning for "6=," this property is written - \Delta (\Delta) 6= 0. In particular,
of \Delta that require substantially fewer resources, do have
\Delta-measure zero. For example, P has E-measure zero. Indeed, for any fixed c ? 0, DTIME[2 cn ] has
E-measure zero, and DTIME[2 n c
has EXP-measure zero [Lut92].
Apart from formalizing rareness and abundance in complexity theory, resource-bounded martingales
are also used to define the concept of a random set in a resource-bounded setting.
Definition 2.3. A set A is \Delta-random if - \Delta (fAg) 6= 0.
In other words, A is \Delta-random if no \Delta-martingale succeeds on A.
Betting Games
To capture intuitions that have been expressed not only for Lutz measure but also in many earlier
papers on random sequences, we formalize a betting game as an infinite process, rather than as a
Turing machine that has finite computations on string inputs.
Definition 3.1. A betting game G is an oracle Turing machine that maintains a "capital tape"
and a "bet tape," in addition to its standard query tape and worktapes, and works in stages
Beginning each stage i, the capital tape holds a nonnegative rational
number C i\Gamma1 . Initially, C computes a query string x i to bet on, a bet amount B i ,
g. The computation is legal so long as x i does not
belong to the set f x of strings queried in earlier stages. G ends stage i by entering a
special query state. For a given oracle language A, if x i 2 A and b i =+1, or if x
2 A and b
then the new capital is given by C i := C . The query and bet tapes
are blanked, and G proceeds to stage i + 1.
Since we require that G spend the time to write each bet out in full, it does not matter whether
we suppose that the new capital is computed by G itself or updated instantly by the oracle. In this
paper, we lose no generality by not allowing G to "crash" or to loop without writing a next bet
and query. Note that every oracle set A determines a unique infinite computation of G, which we
denote by G A . This includes a unique infinite sequence x 1 query strings, and a unique
sequence telling how the gambler fares against A .
Definition 3.2. A betting machine G runs in time t(n) if for all oracles A, every query of length
made by G A is made in the first t(n) steps of the computation.
A similar definition can be made for space usage, taking into account standard issues such as
whether the query tape counts against the space bound, or whether the query itself is preserved in
read-only mode for further computation by the machine.
Definition 3.3. A betting game G succeeds on a language A, written A 2 S 1 [G], if the sequence
of values C i in the computation G A is unbounded. If A 2 S 1 [G], then we also say G covers A.
Our main motivating example where one may wish not to bet in lexicographic order, or according
to any fixed ordering of strings, is deferred to Section 6. There we will construct an E-betting
game that succeeds on the class of - p
-autoreducible languages, which is not known to have Lutz
measure zero in E or EXP.
We now want to argue that the more liberal requirement of being covered by a time t(n)
betting game, still defines a smallness concept for subclasses of DTIME[t(n)] in the intuitive sense
Lutz established for his measure-zero notion. The following result is a good beginning.
Theorem 3.1 For every time-t(n) betting game G, we can construct a language in DTIME[t(n)]
that is not covered by G.
Proof. Let Q be a non-oracle Turing machine that runs as follows, on any input x. The machine
simulates up to t(jxj) steps of the single computation of G on empty input. Whenever G bets
on and queries a string y, Q gives the answer that causes G to lose money, rejecting in case of a
zero bet. If and when G queries x, Q does likewise. If t(jxj) steps go by without x being queried,
then Q rejects x.
The important point is that Q's answer to a query y 6= x is the same as the answer when Q
is run on input y. The condition that G cannot query a string x of length n after t(n) steps have
elapsed ensures that the decision made by Q when x is not queried does not affect anything else.
Hence Q defines a language on which G never does better than its initial capital C 0 , and so does
not succeed.
In particular, the class E cannot be covered by an E-betting game, nor EXP by an EXP-betting
game. Put another way, the "measure conservation axiom" [Lut92] of Lutz's measure carries over
to betting games.
To really satisfy the intuition of "small," however, it should hold that the union of two small
classes is small. (Moreover, "easy" countable unions of small classes should be small, as in [Lut92].)
Our lack of meeting this "finite union axiom" will later be excused insofar as it has the non-
relativizing consequence BPP 6= EXP. Theorem 3.1 is still good enough for the "measure-like"
results in this paper.
We note also that several robustness properties of Lutz's measure treated in Section 2 carry
over to betting games. This is because we can apply the underlying transformations to the capital
function c G of G, which is defined as follows:
Definition 3.4. Let G be a betting games, and i - 0 an integer.
(a) A play ff of length i is a sequence of i-many oracle answers. Note that ff determines the first
i-many stages of G, together with the query and bet for the next stage.
(b) c G (ff) is the capital C i that G has at the end of the play ff (before the next query).
Note that the function c G is a martingale over plays ff. The proof of Lemma 2.1 works for c G . We
obtain:
Lemma 3.2 ("Slow-But-Sure Winnings" lemma for betting games) Let G be a betting
game that runs in time t(n). Then we can construct a betting game G 0 running in time O(t(n))
such that S 1 [G] makes the same queries in the same order as G, and:
2:
Proof. The proof of Lemma 2.1 carries over. The only additional observation is that c G 0 can be
constructed on the fly, and this allows G 0 to run in time O(t(n)).
To begin comparing betting games and martingales, we note first that the latter can be considered
a direct special case of betting games. Say a betting game G is lex-limited if for all oracles
A, the sequence x 1 queries made by G A is in lex order. (It need not equal the lex
enumeration
Theorem 3.3 Let T (n) be a collection of time bounds that is closed under multiplication by 2 n ,
such as 2 O(n) or 2 n O(1)
. Then a class C has time-T (n) measure zero iff C is covered by a time-T (n)
lex-limited betting game.
Proof. From a martingale d to a betting game G, each stage i of G A bets on s i an amount B i with
is the first bits of the characteristic sequence of
A. This takes O(2 n ) evaluations of d to run G up through queries of length n, hence the hypothesis
on the time bounds T (n). In the other direction, when G is lex-limited, one can simulate G on a
finite initial segment w of its oracle up to a stage where all queries have been answered by w and
G will make no further queries in the domain of w. One can then define d(w) to be the capital
entering this stage. That this is a martingale and fulfills the success and run-time requirements is
left to the reader.
Hence in particular for measure on E and EXP, martingales are equivalent to betting games constrained
to bet in lex order. Now we will see how we can transform a general betting game into an
equivalent martingale.
4 From Betting Games to Martingales
This section associates to every betting game G a martingale dG such that S 1 [G] ' S 1 [d G ], and
begins examining the complexity of dG . Before defining dG , however, we pause to discuss some
subtleties of betting games and their computations.
Given a finite initial segment w of an oracle language A, one can define the partial computation
G w of the betting game up to the stage i at which it first makes a query x i that is not in the domain
of w. Define d(w) to be the capital C i\Gamma1 that G had entering this stage. It is tempting to think
that d is a martingale and succeeds on all A for which G succeeds-but neither statement is true
in general. The most important reason is that d may fail to be a martingale.
To see this, suppose x i itself is the lexicographically least string not in the domain of w. That
is, x i is indexed by the bit b of wb, and w1 v A iff x i 2 A. It is possible that G A makes a small
(or even zero) bet on x i , and then goes back to make more bets in the domain of w, winning lots of
money on them. The definitions of both d(w0) and d(w1) will then reflect these added winnings,
and both values will be greater than d(w). For example, suppose G A first puts a zero bet on x
then bets all of its money on x not being in A, and then proceeds with x
Put another way, a finite initial segment w may carry much more "winnings potential" than
the above definition of d(w) reflects. To capture this potential, one needs to consider potential plays
of the betting game outside the domain of w. Happily, one can bound the length of the considered
plays via the running time function t of G. Let n be the maximum length of a string indexed by
(jwj)c. Then after t(n) steps, G cannot query any more strings in the domain of
so w's potential is exhausted. We will define dG (w) as an average value of those plays that can
happen, given the query answers fixed by w. We use the following definitions and notation:
Definition 4.1. For any t(n) time-bounded betting game G and string w 2 \Sigma   , define:
(a) A play ff is t-maximal if G completes the first jffj stages, but not the query and bet of the
next stage, within t steps.
(b) A play ff is G-consistent with w, written ff -G w, if for all stages j such that the queried
string x j is in the domain of w, ff That is, ff is a play that could possibly happen
given the information in w. Also let m(ff; w) stand for the number of such stages j whose
query is answered by w.
(c) Finally, put dG
ff t(n)\Gammamaximal;ff- Gw
The weight 2 m(ff;w)\Gammajffj in Equation (7) has the following meaning. Suppose we extend the simulation
of G w by flipping a coin for every query outside the domain of w, for exactly i stages. Then the
number of coin-flips in the resulting play ff of length i is its probability.
Thus dG (w) returns the suitably-weighted average of t(n)-step computations of G with w fixed.
The interested reader may verify that this is the same as averaging d(wv) over all v of length 2 t(n)
(or any fixed longer length), where d is the non-martingale defined at the beginning of this section.
Lemma 4.1 The function dG (w) is a martingale.
Proof. First we argue that
Observe that when ff This is because none of
the queries answered by fi can be in the domain of w, else the definition of G running in time t(n)
would be violated. Likewise if ff -G w then m(ff Finally, since c G is a martingale,
These facts combine to show the equality of (7) and (8).
By the same argument, the right-hand side of (8) is unchanged on replacing "t(n)" by any
Now consider w such that jwj + 1 is not a power of 2. Then the "n" for w0 and w1 is the same
as the "n" for dG (w). Let P 0 stand for the set of ff of length t(n) that are G-consistent with w0
but not with w1, P 1 for those that are G-consistent with w1 but not w0, and P for those that are
consistent with both. Then the set f ff : equals the disjoint union of P ,
and P 1 . Furthermore, for ff 2 P 0 we have m(ff;
dG (w0)+d G
c G (ff)2 m(ff;w1)\Gammat(n)
c G (ff)2 m(ff;w)\Gammat(n)
c G (ff)2 m(ff;w)\Gammat(n)
Finally, if jwj a power of 2, then dG (w0) and dG (w1) use t 0 their length of
ff. However, by the first part of this proof, we can replace t(n) by t 0 in the definition of dG (w)
without changing its value, and then the second part goes through the same way for t 0 . Hence dG
is a martingale.
It is still the case, however, that dG may not succeed on the languages on which the betting
game G succeeds. To ensure this, we first use Lemma 3.2 to place betting games G into a suitable
"normal form" satisfying the sure-winnings condition (5).
Lemma 4.2 If G is a betting game satisfying the sure-winnings condition (5), then S 1 [G] '
Proof. First, let A 2 S 1 [G], and fix k ? 0. Find a finite initial segment w v A long enough to
answer every query made in a play ff of G such that c G (ff) long enough to make t(n)
in the definition of dG (w) (Equation 7) greater than jffj. Then every ff 0 of length t(n) such that
has the form ff fffi. The sure-winnings condition (5) implies that the right-hand side of
defining dG (w) is an average over terms that all have size at least k. Hence dG (w) - k. Letting
k grow to infinity gives A 2 S 1 [d G ].
Now we turn our attention to the complexity of dG . If G is a time-t(n) betting game, it is clear
that dG can be computed deterministically in O(t(n)) space, because we need only cycle through
all ff of length t(n), and all the items in (7) are computable in space O(t(n)). In particular, every
E-betting game can be simulated by an ESPACE-martingale, and every EXP-betting game by an
EXPSPACE-martingale. However, we show in the next section that one can estimate dG (w) well
without having to cycle through all the ff, using a pseudo-random generator to "sample" only a
very small fraction of them.
5 Sampling Results
First we determine the accuracy to which we need to estimate the values d(w) of a hard-to-compute
martingale. We state a stronger version of the result than we need in this section. We will use the
strenghtening in Sections 6.2 and 6.3. Recall that
Lemma 5.1 Let d be a martingale that is active only on J ' f 0; 1 g   , and let [ffl(i)] 1
i=0 be a non-negative
sequence such that
converges to a number K. Suppose we can compute in time
t(n) a function g(w) such that jg(w) \Gamma d(w)j - ffl(N ) for all w of length N . Then there is a
martingale d 0 computable in time O(2 n t(n)) such that for all
In this section, we will apply Lemma 5.1 with In
Section 6.3 we will apply Lemma 5.1 in cases where J is finite.
Proof. First note that for any w (with
In case inductively define:
Note that d 0 satisfies the average law (1), and that we can compute d 0 (w) in time O(2 n t(n)).
By induction on jwj, we can show using the estimate (9) that
It follows that
and that
This establishes the lemma in case . The generalization to other subsets J of
is left to the reader.
Next, we will specify precisely which function f G we will sample in order to estimate dG , and
how we will do it.
Let G be a t(n) time-bounded betting game. Consider a prefix w, and let n denote the largest
length of a string in the domain of w. With any string ae of length t(n), we can associate a unique
"play of the game" G defined by using w to answer queries in the domain of w, and the successive
bits of ae to answer queries outside it. We can stop this play after t(n) steps-so that the stopped
play is a t(n)-maximal ff-and then define f G (w; ae) to be the capital c G (ff). Note that we can
compute f G (w; ae) in linear time, i.e. in time O(jwj t(n)). The proportion of strings ae of length
t(n) that map to the same play ff is exactly the weight 2 m(ff;w)\Gammajffj in the equation (7) for dG (w).
Letting E stand for mathematical expectation, this gives us:
We will apply two techniques to obtain a good approximation g(w) to this average:
ffl sampling using pseudo-random generators, and
ffl approximate counting using alternation.
5.1 Sampling via Pseudo-Random Generators
First, we need some relevant background on pseudo-random generators.
Definition 5.1 ([NW94]). (a) The hardness HA (n) of a set A at length n is the largest integer
s such that for any circuit C of size at most s with n inputs,
where x is uniformly distributed over \Sigma n .
(b) A pseudo-random generator (PRG) is a function D that, for each n, maps \Sigma n into \Sigma r(n) where
n. The function r is called the stretching of D. We say that D is computable in C if
every bit of D(y) is computable in C, given y and the index of the bit in binary.
(c) The security SD (n) of D at length n is the largest integer s such that for any circuit C of size
at most s with r(n) inputs
s
where x is uniformly distributed over \Sigma r(n) and y over \Sigma n .
For our purposes, we will need a pseudo-random generator computable in E that stretches seeds
super-polynomially and has super-polynomial security at infinitely many lengths. We will use the
one provided by the following theorem.
Theorem 5.2 If MA 6= EXP, there is a pseudo-random generator D computable in E with stretching
'(log n) such that for any integer k, SD (n) - n k for infinitely many n.
The proof follows directly from the next results of Babai, Fortnow, Nisan and Wigderson [BFNW93],
and Nisan and Wigderson [NW94], combined with some padding.
Theorem 5.3 ([BFNW93]) If MA 6= EXP, there is a set A 2 EXP such that for any integer k,
for infinitely many n.
Theorem 5.4 ([NW94]) Given any set A 2 EXP, there is a pseudo-random generator D computable
in EXP with stretching n '(log n) such that SD
n)=n).
We will also make use of pseudo-random generators with exponential security and computable
in exponential time. They have the interesting property that we can blow up the stretching exponentially
without significantly reducing the security.
Theorem 5.5 ([GGM86]) If there is a pseudo-random generator computable in EXP (respec-
tively, E) with security 2
n) ), then there is such a pseudo-random generator
with stretching 2 p(n) for any fixed polynomial p.
The following general result shows how PRGs can be used to approximate averages. It provides
the accuracy and time bounds needed for applying Lemma 5.1 to get the desired martingale.
Theorem 5.6 Let D be a pseudo-random generator computable in time ffi(n) and with stretching
r(n). be a linear-time computable function, and s;
constructible functions such that s(N) - N and the following relations hold for any integer N - 0,
Then we can approximate
to within N \Gamma2 in time O(2 m(N) \Delta (s(N)
Proof. For any integer N - 0, let IN be a partition of the interval [\GammaR(N ); R(N )] into subintervals
of length 1
. Note that jI N I 2 IN and any string w of length
The predicate underlying -(I; w) can be computed by circuits of size O(s(N )). Since SD (m(N)) 2
!(s(N )), it follows that
approximates -(I; w) to within an additive error of (S D (m(N))) \Gamma1 , and we can compute it in time
We define the approximation ~ h(w) for h(w) as
I2IN
~
Since we can write h(w) as
I2IN
we can bound the approximation error as follows:
I2IN
I2IN
Computing ~ h(w) requires jI N evaluations of ~ -, which results in the claimed upper
bound for the time complexity of ~ h.
Now, we would like to apply Theorem 5.6 to approximate by (7) to within N \Gamma2 ,
by setting However, for a general betting game G running in time
t(n), we can only guarantee an upper bound of R(N) t(log N) on jf(w; ae)j. Since SD can be at
most exponential, condition (10) would force m(N) to be \Omega\Gamma t(log N )). In that case, Theorem 5.6
can only yield an approximation computable in time 2 O(t(log N)) . However , we can assume wlog.
that G satisfies the slow-winnings condition (6) of Lemma 3.2, in which case an upper bound of
holds. Then the term s(N) in the right-hand side of (10) dominates, provided
n) .
Taking everything together, we obtain the following result about transforming E- and EXP-
betting games into equivalent E- respectively EXP-martingales:
Theorem 5.7 If there is a pseudo-random generator computable in E with security 2
n) , then for
every E-betting game G, there exists an E-martingale d such that S 1 [G] ' S 1 [d]. If there is a
pseudo-random generator computable in EXP with security 2
n\Omega\Gamma/1 , then for every EXP-betting game
G, there exists an EXP-martingale d such that S 1 [G] ' S 1 [d].
Proof. By Lemma 3.2, we can assume that c G satisfies both the sure-winnings condition (5) as
well as the slow-winnings condition (6). Because of Lemma 4.2 and Lemma 5.1 (since the series
suffices to approximate the function dG (w) given by (7) to within N \Gamma2 in
, where
Under the given hypothesis for E, we can meet the conditions for applying Theorem 5.6 to
we obtain the approximation
of dG we need. The same holds in like manner for EXP, for which we have s(N) 2 2 (log N) O(1)
5.2 Approximate Counting using Alternation
Instead of hypothesizing the existence of strong pseudo-random generators, we can also use the
following theorem of Stockmeyer on approximate counting.
Theorem 5.8 ([Sto83]) For any h 2 #P and any polynomial p, there is a function g 2
3 such
that for any input w of length N ,
Theorem 5.9 (a) If then for every E-betting game G, there exists an E-martingale d
such that S 1 [G] ' S 1 [d].
(b) If NP ' DTIME[2 (log n) O(1)
then for every EXP-betting game G, there exists an EXP-
martingale d such that S 1 [G] ' S 1 [d].
The proof plugs (12) into the above sampling results in a similar manner.
6 Autoreducible Sets
An oracle Turing machine M is said to autoreduce a language A if L(M A and for all strings
M A on input x does not query x. That is, one can learn the membership of x by querying
strings other than x itself. If M runs in polynomial time, then A is P-autoreducible-we also write
-autoreducible. If M is also non-adaptive, then A is - p
-autoreducible.
One can always code M so that for all oracles, it never queries its own input-then we call
M an autoreduction. Hence we can define an effective enumeration [M i
of polynomial-time
autoreductions, such that a language A is autoreducible iff there exists an i such that L(M A
(For a technical aside: the same M i may autoreduce different languages A, and some M i may
autoreduce no languages at all.) The same goes for - p
-autoreductions.
Autoreducible sets were brought to the polynomial-time context by Ambos-Spies [AS84]. Their
importance was further argued by Buhrman, Fortnow, Van Melkebeek, and Torenvliet [BFvMT98],
who showed that all - p
T -complete sets for EXP are - p
-autoreducible (while some complete sets
for other classes are not). Here we demonstrate that autoreducible sets are important for testing
the power of resource-bounded measure.
6.1 Adaptively Autoreducible Sets
As stated in the Introduction, if the - p
T -autoreducible sets in EXP (or sufficiently the - p
sets for EXP) are covered by an EXP-martingale, then EXP 6= BPP, a non-relativizing consequence.
However, it is easy to cover them by an E-betting game. Indeed, the betting game uses its adaptive
freedom only to "look ahead" at the membership of lexicographically greater strings, betting nothing
on them.
Theorem 6.1 There is an E-betting game G that succeeds on all - p
-autoreducible sets.
Proof. Let be an enumeration of - p
T -autoreductions such that each M i runs in time
on inputs of length n. Our betting game G regards its capital as composed of infinitely many
"shares" c i , one for each M i . Initially, c Letting h\Delta; \Deltai be a standard pairing function,
inductively define n
During a stage makes a query of
length less than n looks up the answer from its table of past queries. Whenever M i makes
a query of length n s\Gamma1 or more, G places a bet of zero on that string and makes the same query.
Then G bets all of the share c i on 0 n s\Gamma1 according to the answer of the simulation of M i . Finally,
G "cleans up" by putting zero bets on all strings with length in [n that were not queries in
the previous steps.
If M i autoreduces A, then share c i doubles in value at each stage hi; ji, and makes the total
capital grow to infinity. And G runs in time 2 O(n) -indeed, only the "cleanup" phase needs this
much time.
Corollary 6.2 Each of the following statements implies BPP 6= EXP:
1. The class of - p
T -autoreducible sets has E-measure zero.
2. The class of - p
-complete sets for EXP has E-measure zero.
3. E-betting games and E-martingales are equivalent.
4. E-betting games have the finite union property.
The same holds if we replace E by EXP in these statements.
Proof. Let C stand for the class of languages that are not - p
-hard for BPP. Allender and
Strauss [AS94] showed that C has E-measure zero, so trivially it is also covered by an E-betting
game. Now let D stand for the class of - p
-complete sets for EXP. By Theorem 6.1 and the result
of [BFvMT98] cited above, D is covered by an E-betting game.
contains all of EXP, and:
ffl If D would have E-measure zero, so would C [ D and hence EXP, contradicting the measure
conservation property of Lutz measure.
ffl If E-betting games would have the finite-union property, then C [ D and EXP would be
covered by an E-betting game, contradicting Theorem 3.1.
Since (1) implies (2), and (3) implies (4), these observations suffice to establish the corollary for E.
The proof for EXP is similar.
Since there is an oracle A giving EXP A = BPP A [Hel86], this shows that relativizable techniques
cannot establish the equivalence of E-martingales and E-betting games, nor of EXP-martingales
and EXP-betting games. They cannot refute it either, since there are oracles relative to which
strong PRGs exist-all "random" oracles, in fact.
6.2 Non-Adaptively Autoreducible Sets
It is tempting to think that the non-adaptively P-autoreducible sets should have E-measure zero,
or at least EXP-measure zero, insofar as betting games are the adaptive cousins of martingales.
However, it is not just adaptiveness but also the freedom to bet out of the fixed lexicographic order
that adds power to betting games. If one carries out the proof of Theorem 6.1 to cover the class of
-autoreducible sets, using an enumeration [M i ] of - p
-autoreductions, one obtains a non-adaptive
E-betting game (defined formally below) that (independent of its oracle) bets on all strings in order
given by a single permutation of \Sigma   . The permutation itself is E-computable. It might seem that an
E-martingale should be able to "un-twist" the permutation and succeed on all these sets. However,
our next results, which strengthen the above corollary, close the same "non-relativizing" door on
proving this with current techniques.
Theorem 6.3 For any k - 1, the - p
tt -complete sets for \Delta p
are - p
-autoreducible.
Here is the proof idea, which follows techniques of [BFvMT98] for the theorem that all EXP-
complete sets are - p
-autoreducible. Call a closed propositional formula that has at most k blocks
of like quantifiers (i.e., at most k \Gamma 1 quantifier alternations) a "QBF k formula," and let TQBF k
stand for the set of true QBF formulas. Let A be a - p
tt -complete set for \Delta p
k . Since
TQBF k is \Sigma p
k -hard, there is a deterministic polynomial-time oracle Turing machine M that accepts
A with oracle TQBF k . Let q(x; i) stand for the i-th oracle query made by M on input x. Whether
belongs to TQBF k forms a \Delta p
-question, so we can - p
-reduce it to A. It is possible that
this latter reduction will include x itself among its queries. Let b
i denote the answer it gives to
the question provided that any query to x is answered "yes," and similarly define
i in case x is
answered "no."
i , which holds in particular if x is not queried, then we know the correct answer
b i to the i-th query. If this situation occurs for all queries, we are done: We just have to run
M on input x using the b i 's as answers to the oracle queries. The b i 's themselves are obtained
without submitting the (possibly adaptive) queries made by M , but rather by applying the latter
tt -reduction to A to the pair hx; ii, and without submitting any query on x itself. Hence this
process satisfies the requirements of a - p
tt -autoreduction of A for the particular input x.
Now suppose that b +
for some i, and let i be minimal. Then we will have two opponents
play the k-round game underlying the QBF k -formula that constitutes the i-th oracle query. One
player claims that b +
i is the correct value for b i , which is equivalent to claiming that x 2 A, while
the other claims that b \Gamma
i is correct and that
A. Write -A
A. The players' strategies will consist of computing the game history so far, determining their
optimal next move, - p
tt -reducing this computation to A, and finally producing the result of this
reduction under their respective assumption about -A (x). This approach will allow us to recover
the game history in polynomial time with non-adaptive queries to A different from x. Moreover,
it will guarantee that the opponent making the correct assumption about -A (x) plays optimally.
Since this opponent is also the one claiming the correct value for b i , he will win the game. So, we
output the winner's value for b i .
It remains to show that we can compute the above strategies in deterministic polynomial time
with a \Sigma p
oracle, i.e. in FP \Sigma p
k . It seems crucial that the number k of alternations be constant here.
Proof. (of Theorem 6.3) Let A be a - p
tt -complete set for \Delta p
accepted by the polynomial-time
oracle Turing machine M with oracle TQBF k . Let q(x; i) denote the i-th oracle query of M TQBF k
on input x. Then q(x; i) can be written in the form (9y 1 )(8y
stand for the vectors of variables quantified in each block, or in the opposite form beginning
with the block (8y 1 ). By reasonable abuse of notation, we also ley y r stand for a string
of 0-1 assignments to the variables in the r-th block. Without loss of generality, we may suppose
every oracle query made by M has this form where each y j is a string of length jxj c , and M makes
exactly jxj c queries, taking the constant c from the polynomial time bound on M . Note that the
function q belongs to FP \Sigma p
k . Hence the language
belongs to \Delta p
k+1 . Since A is - p
k+1 , there is a polynomial-time nonadaptive oracle
that accepts L 0 with oracle A. Now define b
We define languages
-reductions inductively
as follows:
k. The set L ' consists of all pairs hx; ji with 1 - j - jxj c , such that there
is a smallest
(x), and the following condition holds. For
let the s-th bit of y r equal
r (hx; si)
otherwise. We put hx; ji into L ' iff there is a lexicographically least y ' such that
and the j-th bit of y ' is set to 1. The form of this definition shows that L ' belongs to \Delta p
. Hence
we can take N ' to be a polynomial-time non-adaptive oracle TM that accepts L ' with oracle A.
Now, we construct a - p
-autoreduction for A. On input x, we compute b
as well as y (b)
r for b 2 f0; 1g and 1 - r - jxj c . The latter quantity y (b)
r is defined as
follows: for 1 - s - jxj c , the s-th bit of y (b)
r equals N A[fxg
r (hx; si) if r j b mod 2, and N Anfxg
r (hx; si)
otherwise. Note that we can compute all these values in polynomial time by making non-adaptive
queries to A none of which equals x.
run M on input x using b
as the
answer to the i-th oracle query. Since it always holds that at least one of b
the correct oracle answer b i (x), we faithfully simulate M on input x, and hence compute -A (x)
correctly.
Otherwise, let i be the first index for which b +
i, we can determine q(x; i) by simulating M on input x until it asks the i-th query. We then
k )], and claim this value equals -A (x).
In order to prove the claim, consider the game history y (b
k . The opponent
claiming the correct value for b i (x) gets to play the rounds that allow him to win the game
(provided he plays well) no matter what the other player does. Since the former opponent is also
the one making the correct assumption about -A (x), an inductive argument shows that he plays
optimally: At his stages ', the string y ' in the above construction of L ' exists, and he plays it.
The key for the induction is that at later stages ' 0 ? ', the value of y r for the value
of y ' at stage '. So, the player with the correct assumption about -A (x) wins the game-that is,
his guess for b i (x) (and not the other player's guess).
In order to formalize the strengthening of Corollary 6.2 that results from Theorem 6.3, we call
a betting game G non-adaptive if the infinite sequence x 1 of queries G A makes is the
same for all oracles A. If G runs in 2 O(n) time, and this sequence hits all strings in \Sigma   , then the
permutation - of the standard ordering s defined by -(s computable and
invertible in 2 O(n) time. It is computable in this amount of time because in order to hit all strings,
G must bet on all strings in f 0; 1 g n within the first 2 O(n) steps. Hence its ith bet must be made in
a number of steps that is singly-exponential in the length of s i . And to compute - need
only be run for 2 O(jx i j) steps, since it cannot query x i after this time. Since - and its inverse are
both E-computable, - is a reasonable candidate to replace lexicographic ordering in the definition
of E-martingales, and likewise for EXP-martingales. We say a class C has -E-measure zero if C
can be covered by an E-martingale that interprets its input as a characteristic string in the order
given by -.
Theorem 6.4 The class of - p
-autoreducible languages can be covered by a non-adaptive E-betting
game. Hence there is an E-computable and invertible permutation - of \Sigma   such that this class has
-E-measure zero.
Proof. With reference to the proof of Theorem 6.1, we can let be an enumeration of
tt -autoreductions such that each M i runs in time n i +i. The machine G in that proof automatically
becomes non-adaptive, and since it queries all strings, it defines a permutation - of \Sigma   as above
with the required properties.
Corollary 6.5 Each of the following statements implies BPP 6= EXP, as do the statements obtained
on replacing "E" by "EXP."
1. The class of - p
tt -autoreducible sets has E-measure zero.
2. The class of - p
tt -complete sets for EXP has E-measure zero.
3. Non-adaptive E-betting games and E-martingales are equivalent.
4. If two classes can be covered by non-adaptive E-betting games, then their union can be covered
by an E-betting game.
5. For all classes C and all E-computable and invertible orderings -, if C has -E-measure zero,
then C has E-measure zero.
Proof. It suffices to make the following two observations to argue that the proof of Corollary 6.2
carries over to the truth-table cases:
ffl The construction of Allender and Strauss [AS94] actually shows that the class of sets that
are not - p
tt -hard for BPP has E-measure zero.
ffl If Theorem 6.3 implies that all - p
tt -complete sets for EXP are - p
because BPP ' \Sigma p
Theorem 6.4 and the finite-unions property of Lutz's measures on E and EXP do the rest.
The last point of Corollary 6.5 asserts that Lutz's definition of measure on E is invariant under all
E-computable and invertible permutations. These permutations include flip from the Introduction
and (crucially) - from Theorem 6.4. Hence this robustness assertion for Lutz's measure implies
BPP 6= EXP. Our "betting-game measure" (both adaptive and non-adaptive) does enjoy this
permutation invariance, but asserting the finite-unions property for it also implies BPP 6= EXP.
The rest of this paper explores conditions under which Lutz's martingales can cover classes of
autoreducible sets, thus attempting to narrow the gap between them and betting games.
6.3 Covering Autoreducible Sets By Martingales
This puts the spotlight on the question: Under what hypotheses can we show that the - p
autoreducible sets have E-measure zero? Any such hypothesis must be strong enough to imply
EXP 6= BPP, but we hope to find hypotheses weaker than assuming the equivalence of (E- or
betting games and martingales, or assuming the finite-union property for betting games.
Do we need strong PRGs to cover the - p
-autoreducible sets? How close can we come to covering
the - p
-autoreducible sets by an E-martingale?
Our final results show that the hypothesis MA 6= EXP suffices. This assumption is only known
to yield PRGs of super-polynomial security (at infinitely many lengths) rather than exponential
security (at almost all lengths). Recall that MA contains both BPP and NP; in fact it is sandwiched
between NP BPP and BPP NP .
Theorem 6.6 If MA 6= EXP, then the class of - p
tt -autoreducible sets has E-measure zero.
We actually obtain a stronger conclusion.
Theorem 6.7 If MA 6= EXP, then the class of languages A autoreducible by polynomial-time
OTMs that always make their queries in lexicographic order has E-measure zero.
To better convey the essential sampling idea, we prove the weaker Theorem 6.6 before the stronger
Theorem 6.7. The extra wrinkle in the latter theorem is to use the PRG twice, to construct the set
of "critical strings" to bet on as well as to compute the martingale.
Proof. (of Theorem 6.6) Let [M i
enumerate the - p
-autoreductions, with each M i running
in time n i . Divide the initial capital into shares s i;m for with each s i;m valued initially
at (1=m 2 )(1=2 i ). For each share s i;m , we will describe a martingale that is only active on a finite
number of strings x, namely only if i - m=2dlog 2 me and m - further only if x
belongs to a set constructed below. We will arrange that whenever M i autoreduces A,
there are infinitely many m such that share s i;m attains a value above 1 (in fact, close to m) along
A. Hence the martingale defined by all the shares succeeds on A. We will also ensure that each
active share's bets on strings of length n are computable in time 2 an , where the constant a is
independent of i. This is enough to make the whole martingale E-computable and complete the
proof.
To describe the betting strategy for s i;m , first construct a set I = I i;m starting with I
and iterating as follows: Let y be the lexicographically least string of length m that does not appear
among queries made by M i on inputs x 2 I. Then add y to I. Do this until I has 3dlog 2 me strings
in it. This is possible because the bound 3dlog 2 mem i on the number of queries M i could possibly
make on inputs in I is less than 2 m . Moreover, 2 m bounds the time needed to construct I. Thus
we have arranged that
for all x; y 2 I with x y, M i (x) does not query y. (13)
Now let J stand for I together with all the queries M i makes on inputs in I. Adapting ideas from
Definition 4.1 to this context, let us define a finite Boolean function to be consistent
with M i on I, written fi - I M i , if for all x 2 I, M i run on input x with oracle answers given by
agrees with the value fi(x). Given a characteristic prefix w, also write fi - w if fi(x) and w(x)
agree on all x in J and the domain of w. Since I and J depend only on i and m, we obtain a
"probability density" function for each share s i;m via
The martingale d i;m standardly associated to this density (as in [Lut92]) is definable inductively
by d i;m
d i;m
(In case - i;m = 0, we already have d i;m (w) = 0, and so both d i;m (w1) and d i;m (w0) are set to 0.)
Note that the values - i;m (wb) for only differ from - i;m (w) if the string x indexed
by b belongs to J ; i.e., d i;m is only active on J .
sufficiently large m, if share s i;m could play the strategy
d i;m , then on A its value would rise to (at least) m=2 i . That is, s i;m would multiply its initial value
by (at least) m 3 .
To see this, first note that for any w v A long enough to contain J in its domain, - i;m
We want to show that for any v short enough to have domain disjoint from I, - i;m
To do this, consider any fixed 0-1 assignment fi 0 to strings in J n I that agrees with v. This
assignment determines the computation of M i on the lexicographically first string x 2 I, using
fi 0 to answer queries, and hence forces the value of fi(x) in order to maintain consistency on I.
This in turn forces the value fi(x 0 ) on the next string x 0 in I, and so on. Hence only one out
of 2 jIj possible completions of fi 0 to fi is consistent with M i on I. Thus - i;m
by (15), and 2
The main obstacle now is that (14), and hence d i;m (w), may not be computable in time 2 an
with a independent of i. The number of assignments fi to count is on the order of 2 jJj
Here is where we use the E-computable PRG D, with super-polynomial stretching and security,
obtained via Theorem 5.2 from the hypothesis MA 6= EXP. For all i and sufficiently large m,
D stretches a seed s of length m into at least 3dlog 2 mem i bits, which are enough to define an
assignment fi s to J (agreeing with any given w). We estimate - i;m (w) by
. By Theorem 5.2 there are infinitely many "good" m such that SD (m) ? m i+4 .
6.9 For all large enough good m, every estimate -
Suppose not. First note that both (14) and (16) do not depend on all of w, just on the up-to-
bits in w that index strings in J , and these can be hard-wired into circuits. The
tests [fi - I M i ] can also be done by circuits of size o(m i+1 ), because a Turing machine computation
of time r can be simulated by circuits of size O(r log r) [PF79]. Hence we get circuits of size less
than SD (m) achieving a discrepancy greater than 1=SD (m), a contradiction. This proves Claim 6.9.
Finally, observe that the proof of Claim 6.8 gives us not only d i;m (w) - i;m (w) \Delta m 3 , but
also d i;m A. For w v A and good m, we thus obtain estimates
g(w) for d i;m (w) within error bounds applying Lemma 5.1 for this
g(w) and yields a martingale d 0
i;m (w) computable in time 2 an , where the constant a is
independent of i. This d 0
i;m (w) is the martingale computed by the actions of share s i;m . Since
actually obtain jd 0
which is stronger than what we needed to conclude that share s i;m returns enough profit. This
completes the proof of Theorem 6.6.
To prove Theorem 6.7, we need to construct sets I = I i;m with properties similar to (13), in the
case where M i is no longer a - p
-autoreduction, but makes its queries in lexicographic order. To
carry out the construction of I, we use the pseudorandom generator D a second time, and actually
need only that M i on input 0 m makes all queries of length ! m before making any query of length
m. To play the modified strategy for share s i;m , however, appears to require that all queries
observe lex order.
Proof. (of Theorem 6.7). Recall that the hypothesis EXP 6= MA yields a PRG D computable in
stretching m bits to r(m) bits such that for all i, all sufficiently large m give r(m) ?
and infinitely many m give hardness SD
be a standard enumeration of
T -autoreductions that are constrained to make their queries in lexicographic order, with each
running in time O(n i ). We need to define strategies for "shares" s i;m such that whenever M i
autoreduces A, there are infinitely many m such that share s i;m grows its initial capital from 1=m 2 2 i
to 1=2 i or more. The strategy for s i;m must still be computable in time 2 am where a is independent
of i.
To compute the strategy for s i;m , we note first that s i;m can be left inactive on strings of
length ! m. The overall running time allowance 2 O(m) permits us to suppose that by the time s i;m
becomes active and needs to be considered, the initial segment w 0 of A (where A is the language
on which the share happens to be playing) that indexes strings of length up to
Hence we may regard w 0 as fixed. For any ff 2 f 0; 1
let M ff
stand for the computation in
which w 0 is used to answer any queries of length ! m and ff is used to answer all other queries.
Because of the order in which M i makes its queries, those queries y answered by w 0 are the same
for all ff, so that those answers can be coded by a string u 0 of length at most m i . Now for any
string y of length equal to m, define
Note that given u 0 and ff, the test "M ff
queries y" can be computed by circuits of size O(m i+1 ).
Hence by using the PRG D at length m, we can compute uniformly in E an approximation PD (x; y)
for P (x; y) such that for infinitely many m, said to be "good" m, all pairs x; y give jP D (x;
Here is the algorithm for constructing I = I i;m . Start with I := ;, and while jIj ! 3 log 2 m,
do the following: Take the lexicographically least string y I such that for all x 2 I,
. The search for such a y will succeed within jIj \Delta m i+4 trials, since for any particular
x, there are fewer than m i+4 strings y overall that will fail the test. (This is so even if m is not good,
because it only involves PD , and because PD involves simulating M D(s)
i over all seeds s.) There
is enough room to find such a y provided which holds for all sufficiently large m.
The whole construction of I can be completed within time 2 2am . It follows that for any sufficiently
large good m and x; y 2 I with x ! y, Pr ff [M ff
At this point we would like to define J to be "I together with the set of strings queried by M i
on inputs in I " as before, but unlike the previous case where M i was non-adaptive, this is not a
valid definition. We acknowledge the dependence of the strings queried by M i on the oracle A by
defining
JA
queries y g:
is, JA has the same size as J in the previous proof. This
latter definition will be OK because M i makes its queries in lexicographic order. Hence the share
s i;m , having already computed I without any reference to A, can determine the strings in JA on
which it should be active on the fly, in lex order. Thus we can well-define a mapping fi from f 0; 1 g r
to f 0; 1 g so that for any k - r, means that the query string y that happens to be kth
in order in the on-the-fly construction of JA is answered "yes" by the oracle. Then we may write
J fi for JA , and then write in place of Most important, given any x 2 I, every
such fi well-defines a computation M fi
i (x). This entitles us to carry over the two "consistency"
definitions from the proof of Theorem 6.6:
Finally, we may apply the latter notion to initial subsets of I, and define for 1 - 3 log m the
predicate
does not query x k .
6.10 For all ', Pr fi [R ' (fi)] - 1=2 ' .
For the base case does not query x 1 , M i being an
autoreduction, and because whether fi - x1 M i depends only on the bit of fi corresponding to x 1 .
Working by induction, suppose Pr fi [R . If R '\Gamma1 (fi) holds, then taking fi 0 to be fi
with the bit corresponding to x ' flipped, R holds. However, at most one of R ' (fi) and
does not query x ' . Hence Pr fi [R ' (fi)] - (1=2)Pr fi [R
and this proves Claim 6.10. (It is possible that neither R ' (fi) nor R ' (fi 0 ) holds, as happens when
some j, but this does not hurt the claim.)
Now we can rejoin the proof of Theorem 6.6 at equation (14), defining the probability density
function - i;m We get a martingale d i;m from - i;m as before, and this
represents an "ideal" strategy for share s i;m to play. The statement corresponding to Claim 6.8 is:
autoreduces A and m is good and sufficiently large, then the ideal strategy for
share s i;m multiplies its value by at least m 3 =2 along A.
To see this, note that we constructed I above so that for all
Pr ff [M ff
It follows that
d3 log me!
me 2 . Hence, using Claim 6.10 with log m, we get:
Since the fi defined by A satisfies fi - I M i , it follows by the same reasoning as in Claim 6.8 that
d i;m profits by at least a fraction of m 3 =2 along A. This proves Claim 6.11.
Finally, we (re-)use the PRG D as before to expand a seed s of length m into a string fi s of
(at least) bits. Given any w, fi s well-defines a fi and a set J fi of size at most r
as constructed above, by using w to answer queries in the domain of w and fi s for everything else.
We again obtain the estimate -
equation (16), with the same time
complexity as before. Now we repeat Claim 6.9 in this new context:
6.12 For all large enough good m, every estimate - i;m (w) satisfies j- i;m (w) \Gamma - i;m (w)j - ffl.
If not, then for some fixed w the estimate fails. The final key point is that because M i always
makes its queries in lexicographic order, the queries in the domain of w that need to be covered are
the same for every fi s . Hence the corresponding bits of w can be hard-wired by circuitry of size at
most r. The test [fi s - I M i ] can thus still be carried out by circuits of size less than m i+1 , and we
reach the same contradiction of the hardness value SD .
Finally, we want to apply Lemma 5.1 to replace d i;m (w) by a martingale d 0
i;m (w) that yields
virtually the same degree of success and is computable in time 2 O(n) . Unlike the truth-table case
we cannot apply Lemma 5.1 verbatim because we no longer have a single small set J that d 0 is
active on. However, along any set A, the values d 0
i;m (w) and d 0
or 1) can differ only
for cases where b indexes a string in the small set J corresponding to A, and the reader may check
that the argument and bounds of Lemma 5.1 go through unscathed in this case. This finishes the
proof of Theorem 6.7.
Conclusions
The initial impetus for this work was a simple question about measure: is the pseudo-randomness
of a characteristic sequence invariant under simple permutations such as that induced by flip in the

Introduction

? The question for flip is tantalizingly still open. However, in Section 6.2 we showed
that establishing a "yes" answer for any permutation that intuitively should preserve the same
complexity-theoretic degree of pseudo-randomness, or even for a single specific such permutation
as that in the simple proof of the non-adaptive version of Theorem 6.1, would have the major
consequence that EXP 6= BPP.
Our "betting games" in themselves are a natural extension of Lutz's measures for deterministic
time classes. They preserve Lutz's original idea of ``betting'' as a means of ``predicting'' membership
in a language, without being tied to a fixed order of which instances one tries to predict, or to a
fixed order of how one goes about gathering information on the language. We have shown some
senses in which betting games are robust and well-behaved. We also contend that some current
defects in the theory of betting games, notably the lack of a finite-unions theorem pending the
status of pseudo-random generators, trade off with lacks in the resource-bounded measure theory,
such as being tied to the lexicographic ordering of strings.
The main open problems in this paper are interesting in connection with recent work by
Impagliazzo and Wigderson [IW98] on the BPP vs. EXP problem. First we remark that the main
result of [IW98] implies that either or BPP has E-measure zero [vM98]. Among
the many measure statements in the last section that imply BPP 6= EXP, the most constrained
and easiest to attack seems to be item 4 in Corollary 6.5. Indeed, in the specific relevant case
starting with the assumption one is given a non-adaptive E-betting game G and
an E-martingale d, and to obtain the desired contradiction that proves BPP 6= EXP, one need
only construct an EXP-betting game G 0 that covers S What we can obtain is a
"randomized" betting game G 00 that flips one coin at successive intervals of input lengths to decide
whether to simulate G or d on that interval. (The intervals come from the proof of Theorem 6.4.)
Any hypothesis that can de-randomize this G 00 implies BPP 6= EXP. We do not know whether the
hypotheses considered in [IW98], some of them shown to follow from BPP 6= EXP itself, are
sufficient to do this.
Stepping back from trying to prove BPP 6= EXP outright or trying to prove that these measure
statements are equivalent to BPP 6= EXP, we also have the problem of narrowing the gap between
BPP 6= EXP and the sufficient condition EXP 6= MA used in our results. Moreover, does EXP 6=
MA suffice to make the - p
T -autoreducible sets have E-measure zero? Does that suffice to simulate
every betting game by a martingale of equivalent complexity? We also inquire whether there exist
oracles relative to which strong PRGs still exist. Our work seems to open many
opportunities to tighten the connections among PRGs, the structure of classes within EXP, and
resource-bounded measure.
The kind of statistical sampling used to obtain martingales in Theorems 5.6 and 5.7
was originally applied to construct martingales from "natural proofs" in [RSC95]. The derandomization
technique from [BFNW93] based on EXP 6= MA that is used here is also applied
in [BvM98, KL98, LSW98]. "Probabilistic martingales" that can use this sampling to simulate
betting games are formalized and studied in [RS98]. This paper also starts the task of determining
how well the betting-game and random-sampling ideas work for measures on classes below E. Even
straightforward attempts to carry over Lutz's definitions to classes below E run into difficulties,
as described in [May94] and [AS94, AS95]. We look toward further applications of our ideas in
lower-level complexity classes.

Acknowledgments

The authors specially thank Klaus Ambos-Spies, Ron Book (pace), and Jack
Lutz for organizing a special Schloss Dagstuhl workshop in July 1996, where preliminary versions
of results and ideas in this paper were presented and extensively discussed. We also thank the
referees for helpful comments.



--R


Measure on small complexity classes
Measure on P: Robustness of the notion.
"Algorithmic Information Theory and Randomness"
Trading group theory for randomness.
BPP has subexponential time simulations unless EXPTIME has publishable proofs.
Using autoreducibility to separate complexity classes.
Separating complexity classes using autoreducibility.
In 13th Annual Symposium on Theoretical Aspects of Computer Science

Hard sets are hard to find.
How to construct random functions.
On relativized exponential and probabilistic complexity classes.
Randomness vs. time: De-randomization under a uniform assumption
On the
A variant of the Kolmogorov concept of complexity.
Resource bounded measure and learn- ability
Almost everywhere high nonuniform complexity.
The quantitative structure of exponential time.
Contributions to the Study of Resource-Bounded Measure
Hardness versus randomness.
Relations among complexity measures.
Probabilistic martingales and BPTIME classes.
Pseudorandom generators
The complexity of approximate counting.
On the measure of BPP.
--TR

--CTR
Klaus Ambos-Spies , Wolfgang Merkle , Jan Reimann , Sebastiaan A. Terwijn, Almost complete sets, Theoretical Computer Science, v.306 n.1-3, p.177-194, 5 September
probabilistic computation;resource-bounded measure;theory of computation;betting games;pseudorandom generators;autoreducibility;complexity classes;sampling;computational complexity;polynomial reductions