The Density of Weakly Complete Problems under Adaptive Reductions.
Given a real number $\alpha < 1$, every language that is weakly $\leq_{n^{\alpha / 2} - {\rm T}}^{{\rm P}} $-hard for  E or weakly $\leq_{n^{\alpha} - {\rm T}}^{\rm P}$-hard for E2 is shown to be exponentially dense.  This simultaneously strengthens the results of Lutz and Mayordomo (1994) and Fu (1995).
Introduction
In the mid-1970's, Meyer[15] proved that every - P
-complete language for exponential
time-in fact, every - P
-hard language for exponential time-is dense. That is,
linear ), DENSE is the class of all dense languages, DENSE c is the
complement of DENSE, and Pm(DENSE c ) is the class of all languages that are - P
-reducible
to non-dense languages. language A 2 f0; 1g   is dense if there is a real number ffl ? 0
such that jA -n
for all sufficiently large n, where .) Since that
time, a major objective of computational complexity theory has been to extend Meyer's
result from - P
m -reductions to - P
-reductions, i.e., to prove that every - P
-hard language for
E is dense. That is, the objective is to prove that
where PT(DENSE c ) is the class of all languages that are - P
T -reducible to non-dense lan-
guages. The importance of this objective derives largely from the fact (noted by Meyer[15])
that the class PT(DENSE c ) contains all languages that have subexponential circuit-size
complexity. language A ' f0; 1g   has subexponential circuit-size complexity if, for every
real number ffl ? 0, for every sufficiently large n, there is an n-input, 1-output Boolean
This research was supported in part by National Science Foundation Grant CCR-9157382, with matching
funds from Rockwell International, Microware Systems Corporation, and Amoco Foundation.
circuit that decides that the set and has fewer than 2 n ffl
gates. Other-
wise, we say that A has exponential circuit-size complexity.) Thus a proof of (2) would tell
us that E contains languages with exponential circuit-size complexity, thereby answering a
major open question concerning the relationship between (uniform) time complexity and
circuit-size complexity. Of course (2) also implies the more modest, but more
famous conjecture, that
where SPARSE is the class of all sparse languages. language A ' f0; 1g   is sparse if
there is a polynomial q(n) such that jA -n j - q(n) for all n 2 N.) As noted by Meyer[15],
the class PT(SPARSE) consists precisely of all languages that have polynomial circuit-size
complexity, so (3) asserts that E contains languages that do not have polynomial circuit-size
complexity.
Knowing (1) and wanting to prove (2), the natural strategy has been to prove results of
the form
for successively larger classes P r (DENSE c ) in the range
The first major step beyond (1) in this program was the proof by Watanabe[17] that
i.e., that every language that is - P
O(log n)\Gammatt -hard for E is dense. The next big step was the
proof by Lutz and Mayordomo[10] that, for every real number ff ! 1,
This improved Watanabe's result from O(log n) truth-table (i.e., nonadaptive) queries to
n ff such queries for ff arbitrarily close to 1 (e.g., to n 0:99 truth-table queries). Moreover,
Lutz and Mayordomo[10] proved (5) by first proving the stronger result that for all ff ! 1,
which implies that every language that is weakly - P
poly )
is dense. language A is weakly - P
r -hard for a complexity class C if -(P r (A) j C) 6= 0, i.e.,
nonnegligible subset of C in the sense of the resource-bounded measure
developed by Lutz[9]. A language A is weakly - P
r -complete for C if A 2 C and A is weakly
r -hard for C. See [12] or [2] for a survey of resource-bounded measure and weak com-
pleteness.) The set of weakly - P
languages for E is now known to have p-measure
in the class C of all languages, while the set of all - P
languages for E has measure 0 unless (which is generally
conjectured to be true), almost every language is weakly - P
n ff \Gammatt -hard, but not - P
for E, so the result of Lutz and Mayordomo [10] is much more general than the fact that
every - P
n ff \Gammatt -hard language for E is dense.
A word on the relationship between hardness notions for E and E 2 is in order here. It
is well known that a language is - P
m -hard for E if and only if it is - P
m -hard for this is
(E). The same equivalence holds for - P
T -hardness. It is also clear that
every language that is - P
n ff \Gammatt -hard for E. However, it is not generally
the case that Pm(P n ff \Gammatt may well be the case that a language can
be - P
n ff \Gammatt -hard for E, but not for E 2 . These same remarks apply to - P
-hardness.
The relationship between weak hardness notions for E and E 2 is somewhat different.
Juedes and Lutz [8] have shown that weak - P
m -hardness for E implies
-hardness for
proof of this fact also works for
T -hardness. However, Juedes and Lutz
[8] also showed that weak - P
m -hardness for does not generally imply
-hardness
for E, and it is reasonable to conjecture (but has not been proven) that the same holds for
-hardness. We further conjecture that the notions of weak - P
and
are incomparable, and similarly for
-hardness.
In any case, (6) implies that, for every ff ! 1, every language that is weakly - P
for either E or E 2 is dense.
Shortly after, but independently of [10], Fu[7] used very different techniques to prove
that, for every ff ! 1,
and
That is, every language that is - P
is dense. These
results do not have the measure-theoretic strength of (6), but they are a major improvement
over previous results on the densities of hard languages in that they hold for Turing
reductions, which have adaptive queries.
In the present paper, we prove results which simultaneously strengthen results of Lutz
and Mayordomo[10] and the results of Fu[7]. Specifically, we prove that, for every ff ! 1,
and
These results imply that every language that is weakly - P
weakly
dense. The proof of (9) and (10) is not a simple extension of
the proof in [10] or the proof in [7], but rather combines ideas from both [10] and [7] with
the martingale dilation technique introduced by Ambos-Spies, Terwijn, and Zheng [3].
Our results also show that the strong hypotheses - p (NP) 6= 0 and - p 2 (NP) 6= 0 (surveyed
in [12] and [2]) have consequences for the densities of adaptively hard languages for NP.
Mahaney [13] proved that
and Ogiwara and Watanabe [16] improved this to
That is, if P 6= NP, then no sparse language can be - P
btt -hard for NP. Lutz and Mayordomo
[10] used (6) to obtain a stronger conclusion from a stronger hypothesis, namely, for all
By and (10), we now have, for all ff ! 1,
and
Thus, if - p (NP) 6= 0, then every language that is - P
n 0:49 \GammaT -hard for NP is dense. If
- p2 (NP) 6= 0, then every language that is - P
n 0:99 \GammaT -hard for NP is dense.
Preliminaries
The Boolean value of a condition, / is
ae
0 if not /:
The standard enumeration of f0; 1g   is s enumeration
induces a total ordering of f0; 1g   which we denote by !.
All languages here are subsets of f0; 1g   . The Cantor space is the set C of all languages.
We identify each language A 2 C with its characteristic sequence, which is the infinite
binary sequence
is the standard enumeration of f0; 1g   . For
A to indicate that w is a prefix of (the characteristic
sequence of) A. The symmetric difference of the two languages A and B is A 4
The cylinder generated by a string w 2 f0; 1g   is the set
Note that C
In this paper, a set X ' C that appears in a probability Pr(X) or a conditional probability
Pr(XjCw ) is regarded as an event in the sample space C with the uniform probability
measure. Thus, for example, Pr(X) is the probability that A 2 X when the language
A ' f0; 1g   is chosen probabilistically by using an independent toss of a fair coin to decide
membership of each string in A. In particular, Pr(Cw . The complement of a set
is the set X
exactly t(n)-time-
computable if there is an algorithm that, on input runs for
at most O(t(k steps and outputs an ordered pair (a; b) 2 Z \Theta Z such
that
b . A function f : N d \Theta f0; 1g   ! R is t(n)-time-computable if
there is an exactly t(n)-time-computable function b
We briefly review those aspects of martingales and resource-bounded measure that are
needed for our main theorem. The reader is referred to [2], [9], [12], or [14] for more thorough
discussion.
A martingale is a function d : f0; 1g   ! [0; 1) such that, for all w 2 f0; 1g   ,
a t(n)-martingale is a martingale that is t(n)-time-computable, and an
exact t(n)-martingale is a (rational-valued) martingale that is exactly t(n)-time-computable.
A martingale d succeeds on a language A 2 C if, for every c 2 N, there exists w v A such
that d(w) ? c. The success set of a martingale d is the set
Cjd succeeds on Ag:
The unitary success set of d is
w2f0;1g
The following result was proven by Juedes and Lutz [8] and independently by Mayor-
domo [14].
Lemma 2.1 (Exact Computation Lemma) Let t : N ! N be nondecreasing with t(n) - n 2 .
Then, for every t(n)-martingale d, there is an exact n
d such that
d].
A sequenceX
a
of series of terms a j;k 2 [0; 1) is uniformly p-convergent if there is a polynomial
such that, for all j; r 2 N,X
a r). The following
sufficient condition for uniform p-convergence is easily verified by routine calculus.
Lemma 2.2 Let a j;k 2 [0; 1) for all N. If there exist a real number ffl ? 0 and a
polynomial N such that a j;k - e \Gammak ffl
for all j; k 2 N with k - g(j), then the seriesX
a are uniformly p-convergent.
A uniform, resource-bounded generalization of the classical first Borel-Cantelli lemma
was proved by Lutz [9]. Here we use the following precise variant of this result.
Theorem 2.3 Let ff; e
ff, and let
be an exactly 2 (log n) ff
-time-computable function with the following two properties.
(i) For each j; k 2 N, the function d j;k defined by d j;k is a martingale.
(ii) The seriesX
are uniformly p-convergent.
Then there is an exact 2 (log n) e
ff
-martingale e
ff such
k=t
d]:
Proof (sketch). Assume the hypothesis, and fix ff
ff. Since
ff
it suffices by Lemma 2.1 to show that there is a 2 (log n) ff 0
martingale d 0 such
k=t
Fix a polynomial testifying that the seriesX
are
uniformly p-convergent, and define
for all w 2 f0; 1g   . Then, for each w 2 f0; 1g   ,
so 1). It is clear by linearity that d 0 is a martingale. To see that (16)
holds, assume that A 2[
k=t
arbitrary. Then there exist
2c) such that A 2 S 1 [d j;k ]. Fix w v A such that d j;k (w) - 1. Then
arbitrary here, it follows that A 2 S 1 [d 0 ], confirming
(16).
To see that d 0 is 2 (log n) ff 0
-time-computable, define dA
follows, using the abbreviation 2.
dA
s
dB
s
2s
s
2s
For all r 2 N and w 2 f0; 1g   , it is clear that
and it is routine to verify the inequalities
dA
dB
whence we have
for all r 2 N and w 2 f0; 1g   . Using formula (17), the time required to compute dC (r; w)
exactly is no greater than
and q is a polynomial. Since q(n) \Delta 2 (log n) ff
it follows that
exactly 2 (log n) ff 0
-time-computable. By (18), then, d 0 is a 2 (log n) ff 0
-martingale.
The proof of our main theorem uses the techniques of weak stochasticity and martingale
dilation, which we briefly review here.
As usual, an advice function is a function h Given a function q
we write ADV(q) for the set of all advice functions h such that jh(n)j - q(n) for all n 2 N.
Given a language B and an advice function h, we define the language
is a standard string-pairing function, e.g., ! x; y ?= 0 jxj 1xy. Given
functions t; we define the advice class
Definition (Lutz and Mayordomo[10], Lutz[11]) For t; language A is
weakly (t; q; -stochastic if, for all B; C 2 DTIME(t)=ADV(q) such that jC =n j -(n) for
all sufficiently large n,
lim
We write WS(t; q; -) for the set of all weakly (t; q; -stochastic languages.
The following result resembles the weak stochasticity theorems proved by Lutz and
Mayordomo [10] and Lutz [11], but gives a more careful upper bound on the time complexity
of the martingale.
Theorem 2.4 (Weak Stochasticity Theorem) Assume that ff; fi; fl; - 2 R satisfy ff -
there is an exact 2 (log n) -
-martingale d such that
Proof. Assume the hypothesis, and assume without loss of generality that ff; fi; fl; - 2 Q .
Fix
) be a
language that is universal for DTIME(2 n ff
) in the following sense. For each
Ng.
Define a function d is not a power of 2, then
where the sets Y i;j;k;y;z are defined as follows. If
is the set of all A 2 C such that
The definition of conditional probability immediately implies that, for each N, the
function d 0
i;j;k is a martingale. Since U 2 DTIME(2 n ff 0
to compute each Pr(Y i;j;k;y;z jCw ) using binomial coefficients is at most O(2 (log(i+j+k)) - 00
steps, so the time required to compute d 0
i;j;k (w) is at most O((2 n fi
steps. Thus d 0 is exactly 2 (log n) - 0
-time-computable.
As in [10] and [11], the Chernoff bound tells us that, for all
whence
e, let
4 , and fix k 0 2 N such that
for all j 2 N. Then g is a polynomial and, for all
It follows by Lemma 2.2 that the seriesX
i;j;k (-), for are uniformly p-convergent.
Theorem 2.3 that there is an exact 2 (log n) -
-martingale d such
k=t
Now assume that A 62 WS(2 n ff
by the definition of weak stochasticity,
we can fix and an infinite set J ' N such that, for
all . For each n 2 J , then, there is a prefix w v A
such that Cw ' Y i;j;k;h 1 (n);h2 (n), whence
i;j;k ]. This argument shows that[
k=t
It follows by (19) that
The technique of martingale dilation was introduced by Ambos-Spies, Terwijn, and
Zheng [3]. It has also been used by Juedes and Lutz[8] and generalized considerably by
Breutzmann and Lutz [6]. We use the notation of [8] here.
The restriction of a string  to a language A ' f0; 1g   is
the string w-A obtained by concatenating the successive bits b i for which s i 2 A. If
strictly increasing and d is a martingale, then the f -dilation of d is
the function f-d : f0; 1g   ! [0; 1) defined by
for all w 2 f0; 1g   .
Lemma 2.5 (Martingale Dilation Lemma - Ambos-Spies, Terwijn, and Zheng[3]) If f :
strictly increasing and d is a martingale, then f-d is also a martingale.
Moreover, for every language A 2 f0; 1g   , if d succeeds on f \Gamma1 (A), then f-d succeeds on A.
Finally, we summarize the most basic ideas of resource-bounded measure in E and E 2 .
A p-martingale is a martingale that is, for some k 2 N, an n k -martingale. A p 2 -martingale
is a martingale that is, for some k 2 N, a 2 (log n) k
-martingale.
Definition (Lutz [9])
1. A set X of languages has p-measure 0, and we write - there is a p-
martingale d such that X ' S 1 [d].
2. A set X of languages has p 2 -measure 0, and we write - there is a
-martingale d such that X ' S 1 [d].
3. A set X of languages has measure 0 in E, and we write
4. A set X of languages has measure 0 in E 2 , and we write -(XjE 2
5. A set X of languages has measure 1 in E, and we write
In this case, we say that contains almost every element of E.
6. A set X of languages has measure 1 in E 2 , and we write -(XjE 2
In this case, we say that contains almost every element of E 2 .
7. The expression -(XjE) 6= 0 means that X does not have measure 0 in E. Note that
this does not assert that "-(XjE)" has some nonzero value. Similarly, the expression
means that X does not have measure 0 in E 2 .
It is shown in [9] that these definitions endow E and E 2 with internal measure structure.
This structure justifies the intuition that, if negligibly small
subset of E (and similarly for
The key to our main theorem is the following lemma, which says that languages that are
-reducible to non-dense languages cannot be very stochastic.
Lemma 3.1 (Main Lemma) For all real numbers ff ! 1 and fi
Proof. Let assume without loss of generality that ff and fi are
rational. Let A 2 P n ff \GammaT (DENSE c ). It suffices to show that A is not weakly
stochastic.
there exist a non-dense language S, a polynomial q(n),
and a q(n)-time-bounded oracle Turing machine M such that A = L(M S ) and, for every
makes exactly bjxj ff cqueries (all distinct) on input x with
oracle B. Call these queries c) in the order in which M makes
them.
For each B 2 f0; 1g   and n 2 N, define an equivalence relation -B;n on f0; 1g -q(n) by
and an equivalence relation jB;n on f0; 1g n by
Note that -B;n has at most 2jB -q(n) j+1 equivalence classes, so jB;n has at most (2jB -q(n) j+
equivalence classes.
2 , and let J be the set of all n 2 N for which the following three conditions
hold.
conditions (ii) and (iii) hold for all sufficiently large n.
S is not dense, condition (i) holds for infinitely many n. Thus the set J is
infinite.
Define an advice function h
be a maximum-cardinality equivalence class of the relation j S;n . For
each
Let
Note that
For each n 2 N, let be the set of all coded pairs
such that x; y
denotes the ith query of M on input w when the successive oracle answers
are be the set of all such coded pairs in C n such that M accepts on input
x when the successive oracle answers are b Finally, define the languages
It is clear that B; C 2 DTIME(2 n ). Also, by our construction of these sets and the advice
function h, for each n 2 N, we have
ae
and
For each n 2 J , if -(n) is the number of equivalence classes of j S;n , then
so
It follows that j(C=h) =n
2 for all n 2 N.
Finally, for all n 2 J ,
Since J is infinite, it follows that
for all n 2 N, this
shows that A is not weakly
)-stochastic.
We now prove our main result.
Theorem 3.2 (Main Theorem) For every real number ff ! 1,
Proof. Let
2. By Theorem 2.4, there is an
exact 2 (log n) 2
-martingale d such that
By Lemma 3.1, we then have
Since d is a p 2 -martingale, this implies that - p2 (P n ff \GammaT (DENSE c
Then f is strictly increasing, so f-d, the f-dilation of d, is a martingale. The time required
to compute f-d(w) is
steps, where w steps to compute w 0 and then
O(2 (log jw 0
steps to compute d(w 0 ).)
Now jw 0 j is bounded above by the number of strings x such that jxj 2 - js jwj
jwj)c, so
Thus the time required to compute f-d(w) is
steps, so f-d is an n 2 -martingale.
Now let A 2 P n ff=2 \GammaT (DENSE c ). Then f
This shows that P n ff=2 \GammaT (DENSE c ) ' S 1 [f-d]. Since f-d is an
We now develop a few consequences of the Main Theorem. The first is immediate.
Corollary 3.3 For every real number ff ! 1,
The following result on the density of weakly complete (or weakly hard) languages now
follows immediately from Corollary 3.3.
Corollary 3.4 For every real number ff ! 1, every language that is weakly - P
for E or weakly - P
Our final two corollaries concern consequences of the strong hypotheses - p (NP) 6= 0
The relative strengths of these hypotheses are indicated by the known
implications
E)
(The leftmost implication was proven by Juedes and Lutz[8]. The remaining implications
follow immediately from elementary properties of resource-bounded measure.)
Corollary 3.5 Let ff ! 1. If - p (NP) 6= 0, then every language that is - P
NP is dense. If - p2 (NP) 6= 0, then every language that is - P
n ff \GammaT -hard for NP is dense.
We conclude by considering the densities of languages to which SAT can be adaptively
reduced.
Definition A function g : N ! N is subradical if log
It is easy to see that a function g is subradical if and only if, for all k ? 0,
n).
(This is the reason for the name "subradical.") Subradical functions include very slow-growing
functions such as log n and (log n) 5 , as well as more rapidly growing functions such
as 2 (log n) 0:99
Corollary 3.6 If - p (NP) 6= 0, g : N ! N is subradical, and SAT - P
dense.
Proof. Assume the hypothesis. Let A 2 NP. Then there is a - P
-reduction f of A to SAT.
Fix a polynomial q(n) such that, for all x 2 f0; 1g   , jf(x)j - q(jxj). Composing f with
the - P
g(n)\GammaT -reduction of SAT to H that we have assumed to exist then gives a - P
reduction of A to H. Since g is subradical, log so for all
sufficiently large n,
4 . Thus A - P
The above argument shows that H is - P
-hard for NP. Since we have assumed
Corollary 3.5 that H is dense.
To put the matter differently, Corollary 3.6 tells us that if SAT is polynomial-time
reducible to a non-dense language with at most 2 (log n) 0:99
adaptive queries, then NP has
measure 0 in E and in E 2 .
Questions
As noted in the introduction, the relationships between weak hardness notions for E and
under reducibilities such as - P
remain to be resolved. Our main theorem
also leaves open the question whether - P
languages for E must be dense when2 - ff ! 1. We are in the curious situation of knowing that the classes P n 0:99 \Gammatt (DENSE c )
and P n 0:49 \GammaT (DENSE c ) have p-measure 0, but not knowing whether P n 0:50 \GammaT (DENSE c ) has
p-measure 0. Indeed, at this time we cannot even prove that E 6' P n 0:50 \GammaT (SPARSE).
Further progress on this matter would be illuminating.



--R



Theoretical Computer Science.
Relative to a random oracle A
On isomorphism and density of NP and other complete sets.
Equivalence of measures of complexity classes
EXP is not polynomial time Turing reducible to sparse sets.
Weak completeness in E and
Almost everywhere high nonuniform complexity
the density of hard languages.
Theoretical Computer Science
The quantitative structure of exponential time
Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis.
Contributions to the Study of Resource-Bounded Measure
Reported in
On polynomial bounded truth-table reducibility of NP sets to sparse sets
On the Structure of Intractable Complexity Classes.
--TR

--CTR
John M. Hitchcock, The size of SPP, Theoretical Computer Science, v.320 n.2-3, p.495-503, June 14, 2004
weakly complete problems;resource-bounded measure;complexity classes;computational complexity;polynomial reductions