Genericity, Randomness, and Polynomial-Time Approximations.
Polynomial-time safe and unsafe approximations for intractable sets were introduced by Meyer and Paterson [Technical Report TM-126, Laboratory for Computer Science, MIT, Cambridge, MA, 1979] and Yesha [SIAM J. Comput., 12 (1983), pp. 411--425], respectively. The question of which sets have optimal safe and unsafe approximations has been investigated  extensively. Duris and Rolim [Lecture Notes in Comput. Sci. 841, Springer-Verlag, Berlin, New York, 1994, pp. 38--51] and Ambos-Spies [Proc. 22nd ICALP, Springer-Verlag, Berlin, New York, 1995, pp. 384--392] showed that the existence of optimal polynomial-time approximations for the safe and unsafe cases is independent. Using the law of the iterated logarithm for p-random sequences (which has been recently proven in [Proc. 11th Conf. Computational Complexity, IEEE Computer Society Press, Piscataway, NJ, 1996, pp. 180--189]), we extend this observation by showing that both the class of polynomial-time $\Delta$-levelable sets and the class of sets which have optimal polynomial-time unsafe approximations have p-measure 0. Hence typical sets in E (in the sense of p-measure) do not have optimal polynomial-time unsafe approximations. We will also establish the relationship between resource bounded genericity concepts and the polynomial-time safe and unsafe approximation concepts.
Introduction
. The notion of polynomial-time safe approximations was introduced
by Meyer and Paterson in [13] (see also [8]). A safe approximation algorithm
for a set A is a polynomial-time algorithm M that on each input x outputs either
do not know) such that all inputs accepted by M are
members of A and no member of A is rejected by M . An approximation algorithm is
optimal if no other polynomial-time algorithm correctly decides infinitely many more
inputs, that is to say, outputs infinitely many more correct 1s or 0s. In Orponen,
Russo, and Sch-oning [14], the existence of optimal approximations was phrased in
terms of P-levelability: a recursive set A is P-levelable if for any deterministic Turing
machine M accepting A and for any polynomial p there is another machine M 0
accepting A and a polynomial p 0 such that for infinitely many elements x of A, M
does not accept x within p(jxj) steps while M 0 accepts x within p 0 (jxj) steps. It is
easy to show that A has an optimal polynomial-time safe approximation if and only
if neither A nor -
A is P-levelable.
The notion of polynomial-time unsafe approximations was introduced by Yesha
in [19]: an unsafe approximation algorithm for a set A is just a standard polynomial-time
bounded deterministic Turing machine M with outputs 1 and 0. Note that,
different from the polynomial-time safe approximations, here we are allowed to make
errors, and we study the amount of inputs on which M are correct. Duris and Rolim
[6] further investigated unsafe approximations and introduced a levelability concept,
\Delta-levelability, which implies the nonexistence of optimal polynomial-time unsafe ap-
proximations. They showed that complete sets for E are \Delta-levelable and there exists
Received by the editors April 22, 1996; accepted for publication (in revised form) March 4, 1997;
published electronically July 7, 1998.
http://www.siam.org/journals/sicomp/28-2/30235.html
y Department of Computer Science, The University of Auckland, Private Bag 92019, Auckland,
New Zealand (wang@cs.auckland.ac.nz).
GENERICITY, RANDOMNESS, AND APPROXIMATIONS 395
an intractable set in E which has an optimal safe approximation but no optimal unsafe
approximation. But they did not succeed in producing an intractable set with optimal
unsafe approximations. Ambos-Spies [1] defined a concept of weak \Delta-levelability
and showed that there exists an intractable set in E which is not weakly \Delta-levelable
(hence it has an optimal unsafe approximation).
Like resource-bounded randomness concepts, different kinds of resource-bounded
genericity concepts were introduced by Ambos-Spies [2], Ambos-Spies, Fleischhack,
and Huwig [3], Fenner [7], and Lutz [9]. It has been proved that resource-bounded
generic sets are useful in providing a coherent picture of complexity classes. These
sets embody the method of diagonalization construction; that is, requirements which
can always be satisfied by finite extensions are automatically satisfied by generic sets.
It was shown in Ambos-Spies, Neis, and Terwijn [4] that the generic sets of Ambos-
Spies are P-immune, and that the class of sets which have optimal safe approximations
is large in the sense of resource-bounded Ambos-Spies category. Mayordomo [11]
has shown that the class of P-immune sets is neither meager nor comeager both in
the sense of resource-bounded Lutz category and in the sense of resource-bounded
Fenner category. We extend this result by showing that the class of sets which have
optimal safe approximations is neither meager nor comeager both in the sense of
resource-bounded Lutz category and in the sense of resource-bounded Fenner category.
Moreover, we will show the following relations between unsafe approximations and
resource-bounded categories.
1. The class of weakly \Delta-levelable sets is neither meager nor comeager in the
sense of resource-bounded Ambos-Spies category [4].
2. The class of weakly \Delta-levelable sets is comeager (is therefore large) in the
sense of resource-bounded general Ambos-Spies [2], Fenner [7], and Lutz [9]
categories.
3. The class of \Delta-levelable sets is neither meager nor comeager in the sense of
resource-bounded general Ambos-Spies [2], Fenner [7], and Lutz [9] categories.
In the last section, we will show the relationship between polynomial-time approximations
and p-measure. Mayordomo [12] has shown that the class of P-bi-immune
sets has p-measure 1. It follows that the class of sets which have optimal polynomial-time
safe approximations has p-measure 1. Using the law of the iterated logarithm
for p-random sequences which we have proved in Wang [16, 17], we will show that the
following hold.
1. The class of \Delta-levelable sets has p-measure 0.
2. The class of sets which have optimal polynomial-time unsafe approximations
have p-measure 0. That is, the class of weakly \Delta-levelable sets has p-measure
1.
3. p-Random sets are weakly \Delta-levelable but not \Delta-levelable.
Hence typical sets in the sense of resource-bounded measure do not have optimal
polynomial-time unsafe approximations.
It should be noted that the above results show that the class of weakly \Delta-levelable
sets is large both in the sense of the different notions of resource-bounded category
and in the sense of resource-bounded measure. That is to say, typical sets in E 2 (in
the sense of resource-bounded category or in the sense of resource-bounded measure)
are weakly \Delta-levelable.
In contrast to the results in this paper, we have recently shown (in [18]) the
following results.
1. There is a p-stochastic set A 2 E 2 which is \Delta-levelable.
2. There is a p-stochastic set A 2 E 2 which has an optimal unsafe approximation

2. Definitions. N and Q(Q + ) are the set of natural numbers and the set of
(nonnegative) rational numbers, respectively. is the binary alphabet, \Sigma
is the set of (finite) binary strings, \Sigma n is the set of binary strings of length n, and
is the set of infinite binary sequences. The length of a string x is denoted by jxj. !
is the length-lexicographical ordering on \Sigma   , and z n (n - 0) is the nth string under
this ordering. - is the empty string. For strings x; y 2 \Sigma   , xy is the concatenation of
x and y, x v y denotes that x is an initial segment of y. For a sequence x 2 \Sigma   [ \Sigma 1
and an integer number n - \Gamma1, x[0::n] denotes the initial segment of length n+1 of x
denotes the ith bit of x, i.e.,
Lowercase letters z from the middle and the end of the alphabet
will denote numbers and strings, respectively. The letter b is reserved for elements of
\Sigma, and lowercase Greek letters -; infinite sequences from \Sigma 1 .
A subset of \Sigma   is called a language, a problem, or simply a set. Capital letters
are used to denote subsets of \Sigma   and boldface capital letters are used to denote
subsets of \Sigma 1 . The cardinality of a language A is denoted by kAk. We identify a
language A with its characteristic function, i.e., x 2 A if and only if 1. The
characteristic sequence of a language A is the infinite sequence A(z 0 )A(z 1
We freely identify a language with its characteristic sequence and the class of all
languages with the set \Sigma 1 . For a language A ' \Sigma   and a string z n 2 \Sigma   , A j'z
. For languages A and B, -
A is the complement of
is the symmetric difference of A and B; A ' B (resp.,
A ae B) denotes that A is a subset of B (resp., A ' B and B 6' A). For a number n,
ng and A ng.
We fix a standard polynomial-time computable and invertible pairing function
-x; yhx; yi on \Sigma   such that, for every string x, there is a real ff(x) ? 0 satisfying
almost all n;
where \Sigma and \Sigma g. We will use
to denote the complexity classes DT IME(poly), DT IME(2 linear ), and
poly ), respectively. Finally, we fix a recursive enumeration fP e : e - 0g of
P such that P e (x) can be computed in O(2 jxj+e ) steps (uniformly in e and x).
We define a finite function to be a partial function from \Sigma   to \Sigma whose domain
is finite. For a finite function oe and a string x 2 \Sigma   , we write oe(x) # if x 2 dom(oe),
and oe(x) " otherwise. For two finite functions oe; - , we say oe and - are compatible if
The concatenation oe- of two finite functions
oe and - is defined as
-. For a set A and a string x, we
identify the characteristic string A j'x with the finite function xg. For
a finite function oe and a set A, oe is extended by A if for all x 2 dom(oe),
3. Genericity versus polynomial-time safe approximations. In this sec-
tion, we summarize some known results on the relationship between the different
notions of resource-bounded genericity and the notion of polynomial-time safe approximations

We first introduce some concepts of resource-bounded genericity.
Definition 3.1. A partial function f from \Sigma   to foe : oe is a finite function g is
dense along a set A if there are infinitely many strings x such that f(A j'x) is defined.
GENERICITY, RANDOMNESS, AND APPROXIMATIONS 397
A set A meets f if, for some x, the finite function extended by A.
Otherwise, A avoids f .
Definition 3.2. A class C of sets is nowhere dense via f if f is dense along all
sets in C and for every set A 2 C, A avoids f .
Definition 3.3. Let F be a class of (partial) functions from \Sigma   to foe : oe is a
finite functiong. A class C of sets is F-meager if there exists a function f 2 F such
that C= [ i2N C i and C i is nowhere dense via f i class C of sets is
F-comeager if -
C is F-meager.
Definition 3.4. A set G is F-generic if G is an element of all F-comeager
classes.
Lemma 3.5 (see [2, 7, 9]). A set G is F-generic if and only if G meets all functions
which are dense along G.
For a class F of functions, each function f 2 F can be considered as a finitary
property P of sets. If f(A j'x) is defined, then all sets extending
the property P . So a set A has the property P if and only if A meets f . f is dense
along A if and only if in a construction of A along the ordering !, where at stage
s of the construction we decide whether or not the string z s belongs to A, there are
infinitely many stages s such that by appropriately defining A(z s ) we can ensure that
A has the property P (that is to say, for some string x, extended by
A).
For different function classes F, we have different notions of F-genericity. In
this paper, we will concentrate on the following four kinds of function classes which
have been investigated by Ambos-Spies [2], Amos-Spies, Neis, and Terwijn [4], Fenner
[7], and Lutz [9], respectively. F 1 is the class of polynomial-time computable partial
functions from \Sigma   to \Sigma; F 2 is the class of polynomial-time computable partial
functions from \Sigma   to foe : oe is a finite functiong; F 3 is the class of polynomial-time
computable total functions from \Sigma   to foe : oe is a finite functiong; and F 4 is the class
of polynomial-time computable total functions from \Sigma   to \Sigma   .
Definition 3.6.
1. (See Ambos-Spies, Neis, and Terwijn [4].) A set G is A-generic if G is F 1 -
generic.
2. (See Ambos-Spies [2].) A set G is general A-generic if G is F 2 -generic.
3. (See Fenner [7].) A set G is F-generic if G is F 3 -generic.
4. (See Lutz [9].) A set G is L-generic if G is F 4 -generic.
Obviously, we have the following implications.
Theorem 3.7.
1. If a set G is general A-generic, then G is A-generic, F-generic, and L-generic.
2. If a set G is F-generic, then G is L-generic.
Proof. The proof is straightforward.
In this paper, we will also study the following
concepts. A set G is Ambos-Spies n k -generic (resp., general Ambos-Spies n k -generic,
Fenner n k -generic, Lutz n k -generic) if and only if G meets all n k -time computable
functions f are dense along G.
Theorem 3.8 (see Ambos-Spies [2]). A class C of sets is meager in the sense
of Ambos-Spies category (resp., general Ambos-Spies category, Fenner category, Lutz
Category) if and only if there exists a number k 2 N such that there is no Ambos-
Spies n k -generic (resp., general Ambos-Spies n k -generic, Lutz n k -generic, Fenner
set in C.
As an example, we show that Ambos-Spies n-generic sets are P-immune.
Theorem 3.9 (see Ambos-Spies, Neis, Terwijn [4]). Let G be an Ambos-Spies
n-generic set. Then G is P-immune.
Proof. For a contradiction assume that A 2 P is an infinite subset of G. Then
the function f : \Sigma   ! \Sigma defined by
is computable in time n and is dense along G. So, by the Ambos-Spies n-genericity
of G, G meets f . By the definition of f , this implies that there exists some string
A such that z
G, a contradiction.
It has been shown (see Mayordomo [12]) that neither F-genericity nor L-genericity
implies P-immunity or non-P-immunity.
A partial set A is defined by a partial characteristic function f : \Sigma   ! \Sigma. A partial
set A is polynomial-time computable if dom(A) 2 P and its partial characteristic
function is computable in polynomial time.
Definition 3.10 (see Meyer and Paterson [13]). A polynomial-time safe approximation
of a set A is a polynomial-time computable partial set Q which is consistent
with A, that is to say, for every string x 2 dom(Q), Q(x). The
approximation Q is optimal if, for every polynomial-time safe approximation Q 0 of A,
Definition 3.11 (see Orponen, Russo, and Sch-oning [14]). A set A is P-levelable
if, for any subset B 2 P of A, there is another subset B of A such that kB 0
1.
Lemma 3.12 (see Orponen, Russo, and Sch-oning [14]). A set A possesses an
optimal polynomial-time safe approximation if and only if neither A nor -
A is P-
levelable.
Proof. The proof is straightforward.
Lemma 3.13. If a set A is P-immune, then A is not P-levelable.
Proof. The proof is straightforward.
Theorem 3.14 (see Ambos-Spies [2]). Let G be an Ambos-Spies n-generic set.
Then neither G nor -
G is P-levelable. That is to say, G has an optimal polynomial-time
safe approximation.
Proof. This follows from Theorem 3.9.
Theorem 3.14 shows that the class of P-levelable sets is "small" in the sense of
resource-bounded (general) Ambos-Spies category.
Corollary 3.15. The class of P-levelable sets is meager in the sense of resource-bounded
(general) Ambos-Spies category.
Now we show that the class of P-levelable sets is neither meager nor comeager in
the sense of resource-bounded Fenner category and Lutz category.
Theorem 3.16.
1. There exists a set G in E 2 which is both F-generic and P-levelable.
2. there exists a set G in E 2 which is F-generic but not P-levelable.
Proof. 1. Let
I be an enumeration of F 3 such that f i (x) can be
computed uniformly in time 2 log k (jxj+i) for some k 2 N .
In the following, we construct a set G in stages which is both F-generic and
P-levelable. In the construction we will ensure that
GENERICITY, RANDOMNESS, AND APPROXIMATIONS 399
In order to ensure that G is P-levelable,
it suffices to satisfy for all e - 0 the following requirements:
To show that the requirements L e (e - 0) ensure that G is P-levelable (fix a subset
of G) we have to define a subset C of G such that C
e such that P Then, by the requirement L e ,
has the required
property.
The strategy for meeting a requirement L e is as follows: if there is a string
to refute the hypothesis of the requirement
trivially met). To ensure that G is F-generic, it suffices to meet for all
the following requirements:
exists a string x such that G extends (G j'x)f e (G j'x).
Because the set I 1 is used to satisfy L e , we will use I 2 to satisfy G e . The strategy
for meeting a requirement G e is as follows: for some string x 2 I 2 , let G extend
Define a priority ordering of the requirements by letting R
Ln . Now we give the construction of G formally.
Stage s.
If G(z s ) has been defined before stage s, then go to stage s + 1.
A requirement L e requires attention if
2. z s 2
3. For all y
A requirement G e requires attention if e ! s, G e has not received attention yet,
and x 2 I 2 for all z s - x - z t where z t is the greatest element in dom((G j'z s )f e (G j'z s )).
Fix the minimal n such that Rn requires attention. If there is no such n, then
let G(z s Otherwise, we say that Rn receives attention. Moreover, if
then let G(z s
z t is the greatest element in dom((G j'z s )f e (G j'z s )) and for a finite function oe and a
number k, f ill 1 (oe;
dom(oe)g.
This completes the construction of G.
It is easy to verify that the set G constructed above is both P-levelable and
F-generic; the details are omitted here.
2. For a general A-generic set G, by Theorem 3.9, G is P-immune. By Theorem
3.7, G is F-generic. Hence, G is F-generic but not P-levelable.
Corollary 3.17. The class of P-levelable sets is neither meager nor comeager
in the sense of resource-bounded Fenner category and Lutz category.
Proof. This follows from Theorem 3.16.
4. Genericity versus polynomial-time unsafe approximations.
Definition 4.1 (see Duris and Rolim [6] and Yesha [19]). A polynomial-time
unsafe approximation of a set A is a set B 2 P. The set A\DeltaB is called the error set
of the approximation. Let f be an unbounded function on the natural numbers. A set
A is \Delta-levelable with density f if, for any set B 2 P, there is another set B
such that
for almost all n 2 N . A set A is \Delta-levelable if A is \Delta-levelable with density f such
that lim n!1
Note that, in Definition 4.1, the density function f is independent of the choice
of
Definition 4.2 (see Ambos-Spies [1]). A polynomial-time unsafe approximation
B of a set A is optimal if, for any approximation B
A set A is weakly \Delta-levelable if, for any polynomial-time unsafe approximation B of
A, there is another polynomial-time unsafe approximation B 0 of A such that
It should be noted that our above definitions are a little different from the original
definitions of Ambos-Spies [1], Duris and Rolim [6], and Yesha [19]. In the original def-
initions, they considered the errors on strings up to certain length (i.e., k(A\DeltaB) -n
instead of errors on strings up to z n (i.e., k(A\DeltaB) j'z n k). But it is easy to check that
all our results except Theorem 5.14 in this paper hold for the original definitions also.
Lemma 4.3 (see Ambos-Spies [1]).
1. A set A is weakly \Delta-levelable if and only if A does not have an optimal
polynomial time unsafe approximation.
2. If a set A is \Delta-levelable then it is weakly \Delta-levelable.
Lemma 4.4. Let A; B be two sets such that A is \Delta-levelable with linear density
and A\DeltaB is sparse. Then B is \Delta-levelable with linear density.
Proof. Let p be the polynomial such that, for all n,
assume that A is \Delta-levelable with density ffn (ff ? 0). Then there is a real number
We will show that B
is \Delta-levelable with density fin.
given any set C 2 P, by \Delta-levelability of A, choose D 2 P such that
for almost all n. Then
for almost all n. Hence, B is \Delta-levelable with density fin.
Theorem 4.5.
1. there exists a set G in E 2 which is both A-generic and \Delta-levelable.
2. there exists a set G in E 2 which is A-generic but not weakly \Delta-levelable.
Proof. 1. Duris and Rolim [6] constructed a set A in E which is \Delta-levelable with
linear density and, in [4], Ambos-Spies, Neis, and Terwijn showed that, for any set
there is an A-generic set B 0 in E 2 such that B \DeltaB 0 is sparse. So, for any set A
which is \Delta-levelable with linear density, there is an A-generic set G in E 2 such that
A\DeltaG is sparse. It follows from Lemma 4.4 that G is \Delta-levelable with linear density.
GENERICITY, RANDOMNESS, AND APPROXIMATIONS 401
2. Ambos-Spies [1, Theorem 3.3] constructed a P-bi-immune set in E which is
not weakly \Delta-levelable. In his proof, he used the requirements
to ensure that the constructed set G is P-bi-immune. In order to guarantee that G is
not weakly \Delta-levelable, he used the requirements
to ensure that will be an optimal unsafe approximation of G. If we
change the requirements BI 2e and BI 2e+1 to the requirements
then a routine modification of the finite injury argument in the proof of Ambos-Spies
[1, Theorem 3.3] can be used to construct an A-generic set G in E 2 which is not
weakly \Delta-levelable. The details are omitted here.
Corollary 4.6. The class of (weakly) \Delta-levelable sets is neither meager nor
comeager in the sense of resource-bounded Ambos-Spies category.
Corollary 4.6 shows that the class of weakly \Delta-levelable sets is neither large nor
small in the sense of resource-bounded Ambos-Spies category. However, as we will
show next, it is large in the sense of resource-bounded general Ambos-Spies category,
resource-bounded Fenner category, and resource-bounded Lutz category.
Theorem 4.7. Let G be a Lutz n 3 -generic set. Then G is weakly \Delta-levelable.
Proof. Let P. We show that -
B witnesses that the unsafe approximation B
of G is not optimal. For any string x, define y, where
if and only if z jxj+j 2 B. Obviously, f is computable in time n 3 . Since G is Lutz
infinitely often. Hence, for any k and n 0 , there exists n ? n 0
such that only if
B. Hence
which implies that G is weakly \Delta-levelable.
Corollary 4.8. The class of weakly \Delta-levelable sets is comeager in the sense
of resource-bounded Lutz, Fenner, and general Ambos-Spies categories.
Proof. This follows from Theorems 3.7, 3.8, and 4.7.
Now we show that the class of \Delta-levelable sets is neither meager nor comeager in
the sense of all these resource-bounded categories we have discussed above.
Theorem 4.9. there exists a set G in E 2 which is both general A-generic and
\Delta-levelable.
Proof. Let
. For each set P e 2 P, let P g(e) be defined
in such a way that
In the following we construct a general A-generic set G which is \Delta-levelable by
keeping P g(e) to witness that the unsafe approximation P e of G is not optimal. Let
be an enumeration of all functions in F 2 such that f i (x) can be computed
uniformly in time 2 log k (jxj+i) for some k 2 N .
The set G is constructed in stages. To ensure that G is general A-generic, it
suffices to meet for all e 2 N the following requirements:
To ensure that G is \Delta-levelable, it suffices to meet for all e; k 2 N the following
requirements, as shown at the end of the proof:
The strategy for meeting a requirement G e is as follows: at stage s, if G e has
not been satisfied yet and f e (G j'z s ) is defined, then let G extend (G j'z s )f e (G j'z s ).
But this action may injure the satisfaction of some requirements L hi;ki and Gm . The
conflict is solved by delaying the action until it will not injure the satisfaction of the
requirements L hi;ki and Gm which have higher priority than G e .
The strategy for meeting a requirement L he;ki is as follows: at stage s, if L he;ki
has not been satisfied yet and P e (z s
a requirement G e becomes satisfied at some stage, it is satisfied forever, so L he;ki
can only be injured finitely often and then it will have a chance to become satisfied
forever.
Stage s.
In this stage, we define the value of G(z s ).
A requirement Gn requires attention if
1.
2. Gn has not been satisfied yet.
3. there exists t - s such that
A. fn (G j'z t ) is defined.
B. G j'z s is consistent with (G j'z t )f n (G j'z t ).
C. For all e; k 2 N such that he; ki ! n, there is at most one he; mi 2 N
such that 0 ffi(he;mi) 2 dom((G j'z t )f n (G j'z t )).
D. For all
(1)
Fix the minimal m such that Gm requires attention, and fix the minimal t in the
above item 3 corresponding to the requirement Gm . If there is no such m, then let
Otherwise we say that Gm receives attention. Moreover, let
for some e; n;
This completes the construction.
We show that all requirements are met by proving a sequence of claims.
Claim 1. Every requirement Gn requires attention at most finitely often.
Proof. The proof is by induction. Fix n and assume that the claim is correct for
all numbers less than n. Then there is a stage s 0 such that no requirement Gm with
attention after stage s 0 . So Gn receives attention at any stage s ? s 0
GENERICITY, RANDOMNESS, AND APPROXIMATIONS 403
at which it requires attention. Hence it is immediate from the construction that Gn
requires attention at most finitely often.
2. Given n 0 2 N , if no requirement Gn (n attention after
stage s 0 and Gn0 requires attention at stage s 0 , then for all he; ki
Proof. The proof is straightforward from the construction.
3. Every requirement Gn is met.
Proof. For a contradiction, fix the minimal n such that Gn is not met. Then fn
is dense along G. We have to show that Gn requires attention infinitely often which
is contrary to Claim 1. Since kP e \DeltaP by the construction
and Claim 2, there will be a stage s 0 such that at all stages s ? s 0 , (1) holds for all
such that he; ki ! n. Hence Gn requires attention at each stage s ? s 0 at
which fn (G j'z s ) is defined.
4. Every requirement L he;ki is met.
Proof. This follows from Claims 2 and 3.
Now we show that G is both A-generic and \Delta-levelable. G is A-generic since all
requirements Gn are met. For he; ki 2 N , let n he;ki be the least number s 0 such that
and let f(n) be the biggest k such that
Then lim
That is to say, G is \Delta-levelable with density f .
Theorem 4.10. there exists a set G in E 2 which is general A-generic but not
\Delta-levelable.
Proof. As in the previous proof, a set G is constructed in stages. To ensure that
G is general A-generic, it suffices to meet for all e 2 N the following requirements:
Fix a set B 2 P. Then the requirements
will ensure that B witnesses the failure of \Delta-levelability of G.
To meet the requirements G e , we use the strategy in Theorem 4.9. The strategy
for meeting a requirement NL he;ki is as follows: at stage s such that P e (z s )
and
this action can be repeated over and over again. Hence kG\DeltaP e k is growing more
quickly than kG\DeltaBk, and eventually the requirement NL he;ki is met at some sufficiently
large stage.
Define a priority ordering of the requirements by letting R
NL he;ki . We now describe the construction of G formally.
Stage s.
In this stage, we define the value of G(z s ).
A requirement NL he;ki requires attention if he; ki ! s and
1.
2.
A requirement Gn requires attention if
1.
2. Gn has not been satisfied yet.
3. there exists t - s such that
A. fn (G j'z t ) is defined.
B. G j'z s is consistent with (G j'z t )f n (G j'z t ).
C. there is no e; k 2 N such that
(1).
(2).
(3). there exists y 2 dom((G j'z t )f n (G j'z t
Fix the minimal m such that Rm requires attention. If there is no such m, let
we say that Rm receives attention. Moreover, if
NL he;ki then let G(z s fix the least t in the above
item 3 corresponding to the requirement Gm . Let G(z s
This completes the construction of G.
It suffices to show that all requirements are met. Note that, by definition of
requiring attention, Rm is met if and only if Rm requires attention at most finitely
often. So, for a contradiction, fix the minimal m such that Rm requires attention
infinitely often. By minimality of m, fix a stage s 0 such that no requirement Rm 0
with
attention after stage s 0 . Then Rm receives attention at any stage
at which Rm requires attention. Now, we first assume that
at some stage s ? s 0 , Gn receives attention and becomes satisfied forever. Finally
assume that Rm = NL he;ki . Then B \DeltaP e is infinite and, at all stages s ? s 0 such that
receives attention; hence G(z s
Since, for all other stages s with s ? s 0 , B(z s rapidly
than G\DeltaB; hence
and NL he;ki is met contrary to assumption.
Corollary 4.11. The class of \Delta-levelable sets is neither meager nor comeager
in the sense of resource-bounded (general) Ambos-Spies, Lutz, and Fenner categories.
Proof. The proof follows from Theorems 3.7, 4.9, and 4.10.
5. Resource-bounded randomness versus polynomial-time approxima-
tions. We first introduce a fragment of Lutz's effective measure theory which will be
sufficient for our investigation.
Definition 5.1. A martingale is a function F : \Sigma
A martingale F succeeds on a sequence - 2 \Sigma 1 if lim sup n F (-[0::n \Gamma
denotes the set of sequences on which the martingale F succeeds.
Definition 5.2 (see Lutz [10]). A set C of infinite sequences has p-measure 0
there is a polynomial-time computable martingale which
GENERICITY, RANDOMNESS, AND APPROXIMATIONS 405
succeeds on every sequence in C. The set C has p-measure 1 (- p
for the complement -
2 Cg of C.
Definition 5.3 (see Lutz [10]). A sequence - is n k -random if, for every n k -time
computable martingale F , lim sup n F that is to say, F does not
succeed on -. A sequence - is p-random if - is n k -random for all k 2 N .
The following theorem is straightforward from the definition.
Theorem 5.4. A set C of infinite sequences has p-measure 0 if and only if there
exists a number k 2 N such that there is no n k -random sequences in C.
Proof. See, e.g., [16].
The relation between p-measure and the class of P-levelable sets is characterized
by the following theorem.
Theorem 5.5 (see Mayordomo [11]). The class of P-bi-immune sets has p-
measure 1.
Corollary 5.6. The class of P-levelable sets has p-measure 0.
Corollary 5.7. The class of sets which possesses optimal polynomial-time safe
approximations has p-measure 1.
Corollary 5.8. For each p-random set A, A has an optimal polynomial-time
safe approximation.
Now we turn our attention to the relations between the p-randomness concept
and the concept of polynomial-time unsafe approximations. In our following proof,
we will use the law of the iterated logarithm for p-random sequences.
Definition 5.9. A sequence - 2 \Sigma 1 satisfies the law of the iterated logarithm if
lim sup
and
lim inf
Theorem 5.10 (see Wang [17]). there exists a number k 2 N such that every
sequence satisfies the law of the iterated logarithm.
For the sake of convenience, we will identify a set with its characteristic sequence.
The symmetric difference of two sets can be characterized by the parity function on
sequences.
Definition 5.11.
1. The parity function \Phi : \Sigma \Theta \Sigma ! \Sigma on bits is defined by
2. The parity function on sequences is defined by
3. The parity function \Phi : \Sigma   \Theta ff : f is a partial function from \Sigma   to \Sigmag ! \Sigma
on strings and functions is defined by x \Phi
defined and b
4. The parity function \Phi : \Sigma 1 \Theta ff : f is a partial function from \Sigma   to \Sigmag !
sequences and functions is defined by - \Phi
defined and b
406 YONGGE WANG
The intuitive meaning of - \Phi f is as follows: Given a sequence - and a number
such that f(-[0::n \Gamma 1]) is defined, we use f to predict the value of -[n] from
the first n bits -[0::n \Gamma 1]. If the prediction is successful, then output 0, else output
1. And - \Phi f is the output sequence.
We first explain a useful technique which is similar to the invariance property of
p-random sequences.
Lemma 5.12. Let - 2 \Sigma 1 be n k -random and f : \Sigma   ! \Sigma be a partial function
computable in time n k such that - \Phi f is an infinite sequence. Then - \Phi f is n
random.
Proof. For a contradiction assume that - \Phi f is not n k\Gamma1 -random and let F : \Sigma   !
be an n k\Gamma1 -martingale that succeeds on - \Phi f . Define by letting
f) for all x 2 \Sigma   . It is a routine to check that F 0 is an n k -martingale.
Moreover, since F succeeds on - \Phi f , F 0 succeeds on -, which is a contradiction with
the hypothesis that - is n k -random.
Lemma 5.13. Let k be the number in Theorem 5.10, and let A; B; C ' \Sigma   be
three sets such that the following conditions hold.
1.
2. kB \DeltaC
3. there exists c 2 N such that, for almost all n,
(2)
Then A is not n k+1 -random.
Proof. Let ff; fi, and fl be the characteristic sequences of A; B, and C, respectively.
By Lemma 5.12, it suffices to define an n 2 -time computable partial function f :
\Sigma   ! \Sigma such that ff \Phi f is an infinite sequence which is not n k -random. Define the
function f by
ae fi[jxj] if fi[jxj] 6= fl[jxj];
undefined if
Then f is n 2 -time computable and, since kB \DeltaC is an infinite sequence.
In order to show that ff \Phi f is not n k -random, we show that ff \Phi f does not satisfy
the law of the iterated logarithm.
We first show that, for all n , the following equation holds:
where l
Let
GENERICITY, RANDOMNESS, AND APPROXIMATIONS 407
Then
l
Obviously, this implies (3).
The condition (2) is equivalent to
(ff \Phi fi)[i] - \Gammac:
So, by (3),
for almost all n, where l j. By (4),
lim inf
0:
Hence, by Theorem 5.10, ff \Phi f is not n k -random. This completes the proof.
Now we are ready to prove our main theorems of this section.
Theorem 5.14. The class of \Delta-levelable sets has p-measure 0.
Proof. Let A be a \Delta-levelable set. Then there is a function f(n) - 0 satisfying
lim polynomial-time computable sets B; C such that for all n,
By Lemma 5.13, A is not n k+1 -random, where k is the number in Theorem 5.10.
So the theorem follows from Theorem 5.4.
Theorem 5.15. The class of sets which have optimal polynomial-time unsafe
approximations has p-measure 0.
Proof. If A has an optimal polynomial-time unsafe approximation, then there is
a polynomial-time computable set B and a number c 2 N such that, for all n,
i.e.,
By Lemma 5.13, A is not n k+1 -random, where k is the number in Theorem 5.10.
So the theorem follows from Theorem 5.4.
Corollary 5.16. The class of sets which are weakly \Delta-levelable but not \Delta-
levelable has p-measure 1.
Corollary 5.17. Every p-random set is weakly \Delta-levelable but not \Delta-levelable.

Acknowledgments

. I would like to thank Professor Ambos-Spies for many comments
on an early version of this paper, and I would like to thank two anonymous
referees for their valuable comments on this paper.



--R

On optimal polynomial time approximations: P-levelability vs

Diagonalizations over polynomial time computable sets
Genericity and measure for exponential time
On the structure of complete sets

Notions of resource-bounded category and genericity

Category and measure in complexity classes
Almost everywhere high nonuniform complexity
Almost every set in exponential time is P-bi-immune
Contributions to the Study of Resource-Bounded Measure
With what frequency are apparently intractable problems difficult?

Optimal approximation of complete sets
Randomness and Complexity.
The law of the iterated logarithm for p-random sequences

On certain polynomial-time truth-table reducibilities of complete sets to sparse sets
--TR
resource bounded genericity;resource bounded randomness;approximation;computational complexity