Measure, Stochasticity, and the Density of Hard Languages.
The main theorem of this paper is that, for every real number $\alpha<1$ (e.g., $\alpha=0.99$), only a measure 0 subset of the languages decidable in exponential time are $\leq^{P}_{n^{\alpha} - tt}$-reducible to languages that are not exponentially dense.  Thus every $\leq^{P}_{n^{\alpha} - tt}$-hard language for E is exponentially dense.  This strengthens Watanabe's 1987 result, that every $\leq^{P}_{(O \log n)-tt}$-hard language for E is exponentially dense.  The combinatorial technique used here, the sequentially most frequent query selection, also gives a new, simpler proof of Watanabe's result.  The main theorem also has implications for the structure of NP under strong hypotheses.  Ogiwara and Watanabe (1991) have shown that the hypothesis $\p\ne\NP$ implies that every $\leq^{P}_{btt}$-hard language for NP is nonsparse (i.e., not polynomially sparse).  Their technique does not appear to allow significant relaxation of either the query bound or the sparseness criterion.  It is shown here that a stronger hypothesis---namely, that NP does not have measure 0 in exponential time---implies the stronger conclusion that, for every real $\alpha<1$, every $\leq^{P}_{n^{\alpha} - tt}$-hard language for NP is exponentially dense.  Evidence is presented that this stronger hypothesis is reasonable.   The proof of the main theorem uses a new, very general weak stochasticity theorem, ensuring that almost every language in E is statistically unpredictable by feasible deterministic algorithms, even with linear nonuniform advice.
Introduction
How dense must a language A ' f0; 1g   be in order to be hard for a complexity
class C? The ongoing investigation of this question, especially important
when has yielded several significant results [3, 11, 19, 21, 22, 29, 30]
over the past 15 years.
Any formalization of this question must specify the class C and give precise
meanings to "hard" and "how dense." The results of this paper concern the
polynomial ), and all subclasses C of
these classes, though we are particularly interested in the case
We will consider the polynomial-time reducibilities - P
(Turing reducibility), - P
btt (bounded truth-table reducibility),
q\Gammatt (truth-table reducibility with q(n) queries on inputs of length
r is any of these reducibilities, we say that
a language A is - P
r -hard for a class C of languages if C ' P r (A), where
r Ag.
Two criteria for "how dense" a language A is have been widely used. A
language A is (polynomially) sparse, and we write A 2 SPARSE, if there is a
polynomial p such that jA-n j - p(n) for all n 2 N, where
A language A is (exponentially) dense, and we write A 2 DENSE, if there is
a real number ffl ? 0 such that jA-n j - 2 n ffl
for all sufficiently large n 2 N. It
is clear that no sparse language is dense.
For any of the above choices of the reducibility - P
r , all known - P
r -hard
languages for NP are dense. Efforts to explain this observation (and similar
observations for other classes and reducibilities) have yielded many results.
(See [8] for a thorough survey.) We mention four such results that are particularly
relevant to the work presented here.
Let DENSE c denote the complement of DENSE, i.e., the set of all languages
A such that, for all ffl ? 0, there exist infinitely many n such that
. For each reducibility - P
r and set S of languages, we write
The first result on the density of hard languages was the following.
Theorem 1.1. (Meyer [21]). Every - P
-hard language for E (or any larger
class) is dense. That is,
):Theorem 1.1 was subsequently improved to truth-table reducibility with
O(log n) queries:
Theorem 1.2. (Watanabe [30, 29]). Every - P
O(log n)\Gammatt -hard language for E
is dense. That is,
):Regarding NP, Berman and Hartmanis [3] conjectured that no sparse language
m -hard for NP, unless This conjecture was subsequently
proven correct:
Theorem 1.3. (Mahaney [19]). If P 6= NP, then no sparse language is
m -hard for NP. That is,
(SPARSE):Theorem 1.3 has recently been extended to truth-table reducibility with
a bounded number of queries:
Theorem 1.4. (Ogiwara and Watanabe [22]). If P 6= NP, then no sparse
language is - P
btt -hard for NP. That is,
(SPARSE):The Main Theorem of this paper, Theorem 4.2, extends Theorems 1.1
and 1.2 above by showing that, for every real ff
a measure 0 subset of the languages in E are - P
-reducible to non-dense
languages. "Measure 0 subset" here refers to the resource-bounded measure
theory of Lutz [15, 16] (also explained in section 3 below). In the notation
of this theory, our Main Theorem says that, for every real ff ! 1,
This means that P n ff \Gammatt (DENSE c )"E is a negligibly small subset of E [15, 16].
In particular, our Main Theorem implies that
i.e., that every - P
n ff \Gammatt -hard language for E is dense. This strengthens Theorem
1.2 above by extending the truth table reducibility from O(log n) queries
to n ff queries (ff ! 1). It is also worth noting that the combinatorial technique
used to prove (1.1) and (1.2)-the sequentially most frequent query
selection-is simpler than Watanabe's direct proof of Theorem 1.2. This
is not surprising, once one considers that our proof of (1.2) via (1.1) is a
resource-bounded instance of the probabilistic method [5, 24, 25, 6, 26, 1],
which exploits the fact that it is often easier to prove the abundance of objects
of a given type than to construct a specific object of that type.
Our proof of (1.1) also shows that, for every real ff ! 1,
Much of our interest in the Main Theorem concerns the class NP and
Theorems 1.3 and 1.4 above. As already noted, for all reducibilities - P
r
discussed in this paper, all known - P
r -hard languages for NP are dense. One
is thus led to ask whether there is a reasonable hypothesis ' such that we
can prove results of the form
for various choices of the reducibility - P
r . (Such a result is much stronger
than the corresponding result
because there is an enormous gap between polynomial and 2 n ffl
growth rates.)
Ogiwara and Watanabe's proof of Theorem 1.4 does not appear to allow
significant relaxation of either the query bound or the sparseness criterion.
In fact, it appears to be beyond current understanding to prove results of
the form (1.4) if ' is "P 6= NP." Karp and Lipton [11] have proven that
That is, the stronger hypothesis \Sigma p
2 gives a stronger conclusion than
those of Theorems 1.3 and 1.4. However, Karp and Lipton's proof does not
appear to allow relaxation of the sparseness criterion, and results of the form
do not appear to be achievable at this time if ' is taken to be "\Sigma p
."
To make progress on matters of this type, Lutz has proposed investigation
of the measure-theoretic hypotheses -(NP E) 6= 0.
These expressions say that NP does not have measure 0 in E 2 ("NP is not a
negligible subset of E 2 ") and that NP does not have measure 0 in
is not a negligible subset of E"), respectively. We now explain the meaning
of these hypotheses. Both are best understood in terms of their negations.
The condition -(NP means that there exist a fixed polynomial q,
a fixed positive quantity c 0 of capital (money), and a fixed betting strategy
(algorithm) oe with the following properties. Given any language A, the
strategy oe bets on the membership or nonmembership of the successive strings
A. Before the betting begins, oe has capital (money)
c 0 . When betting on a string w 2 f0; 1g   , the strategy oe is given as input
the string consisting of the successive bits [[v 2 A]] for all strings v that
precede w in the standard ordering of f0; 1g   . On this input, the strategy
oe computes, in - 2 q(jwj) steps, a fraction r 2 [\Gamma1; 1] of its current capital to
bet that w 2 A. If oe's capital prior to this bet is c, then oe's capital after
the bet is c(1 A. (That is, the betting is
fair.) Finally, the strategy oe is successful, in the sense that, for all A 2 NP,
oe's capital diverges to +1 as the betting progresses through the successive
strings w 2 f0; 1g   .
Thus, the condition -(NP asserts the existence of a fixed 2 q(n) -
time-bounded algorithm for betting successfully on membership of strings in
all languages in NP. If NP ' DTIME(2 r(n) ) for some fixed polynomial r, it
is easy to devise such a strategy, so -(NP Conversely, if -(NP j
then NP is "nearly contained in some fixed DTIME(2 q(n) )," in the
sense that there is a fixed 2 q(n) -time-bounded algorithm oe for successfully
betting on all languages in NP.
There does not appear to be any a priori reason for believing that such
a strategy oe exists, i.e., there does not appear to be any a priori reason
for believing that -(NP Similarly, there does not appear to
be any a priori reason for believing that -(NP j E) = 0. The hypotheses
E) 6= 0 are thus reasonable relative to our current
knowledge. (The hypothesis that the polynomial-time hierarchy separates
into infinitely many levels enjoys a similar status. It may be false, but if it is
false, then a very remarkable algorithm exists.) In fact, Lutz has conjectured
that the conditions -(NP E) 6= 0 may be true.
At this time, we are unable to prove or disprove the widely-believed conjectures
together with the known
implications
E)
means that we are currently unable to prove or disprove the statements
E) 6= 0.
Thus, at present, we are interested in the conditions -(NP
E) 6= 0, not as conjectures, but rather as scientific hypotheses, which
may have more explanatory power than traditional complexity-theoretic hypotheses
such as P 6= NP or the separation of the polynomial-time hierarchy.
Until such time as a mathematical proof or refutation is available, the reasonableness
(or unreasonableness) of such hypotheses can be illuminated only
by investigation of their consequences. Such investigation may indicate, for
example, that the consequences of -(NP en masse, a credible
state of affairs, thereby increasing the reasonableness of this hypothesis. On
the other hand, such investigation may uncover implausible consequences of
or even a proof that -(NP outcome would
contribute to our understanding of NP.
Our Main Theorem implies that, for all ff ! 1,
and
E)
(This is Theorem 4.4 below.) That is, each of the hypotheses -(NP
and -(NP j E) 6= 0 implies that every - P
language for NP is dense.
This conclusion, which is credible and consistent with all observations to date,
is not known to follow from P 6= NP or other traditional complexity-theoretic
hypotheses.
Recent investigation has also shown that the hypotheses -(NP
and -(NP j E) 6= 0 imply that NP contains P-bi-immune languages [20]
and that every - P
-hard language for NP has an exponentially dense, exponentially
hard complexity core [9]. Taken together, such results appear to
indicate that these are reasonable hypotheses which may have considerable
explanatory power.
The proof of our Main Theorem is based on a very general result on the
"weak stochasticity" of languages in E and E 2 . This result, proven in section
3 below, is a useful tool that is of independent interest, as we now explain.
When proving results of the form
where C is a complexity class, it often simplifies matters to have available
some general-purpose randomness properties of languages in C. The term
"general-purpose randomness property" here is heuristic, meaning a set Z of
languages with the following two properties.
(i) Almost every language in C has the property (of membership in) Z.
(This condition, written means that -(Z c
Z c is the complement of Z.)
(ii) It is often the case that, when one wants to prove a result of the form
is easier to prove that X "
For example, in ESPACE=DSPACE(2 linear ), it is known [15, 10] that almost
every language has very high space-bounded Kolmogorov complexity. A variety
of sets X have been shown to have measure 0 in ESPACE, simply by
proving that every element of X has low space-bounded Kolmogorov complexity
[15, 10, 18, 14]. Thus high space-bounded Kolmogorov complexity is
a "general-purpose randomness property" of languages in ESPACE.
In section 3 below, after reviewing some fundamentals of measure in complexity
classes, we prove the Weak Stochasticity Theorem, stating that almost
every language in E, and almost every language in E 2 , is "weakly stochas-
tic," i.e., is statistically unpredictable by feasible deterministic algorithms,
even with linear nonuniform advice. (See section 3 for precise definitions.)
In section 4, then, we give a simple combinatorial proof that no language in
thereby proving the Main Theorem.
It appears that weak stochasticity is, in the above sense, a general-purpose
randomness property of languages in E and E 2 that will be useful in future
investigations.
Preliminaries
In this paper, [[/]] denotes the Boolean value of the condition /, i.e.,
0 if not /
All languages here are sets of binary strings, i.e., sets A ' f0; 1g   . We
identify each language A with its characteristic sequence -A 2 f0; 1g 1 defined
by
is the standard enumeration
of f0; 1g   . Relying on this identification, the set f0; 1g 1 , consisting of all
infinite binary sequences, will be regarded as the set of all languages.
we say that w is a prefix of x,
and write w v x, if . The cylinder
generated by a string w 2 f0; 1g   is
Note that Cw is a set of languages. Note also that C
denotes the empty string.
As noted in section 1, we work with the exponential time complexity
linear polynomial ). It is well-known
that and that NP 6= E.
We let Ng be the set of dyadic rationals. We
also fix a one-to-one pairing function h; i from f0; 1g   \Theta f0; 1g   onto f0; 1g
such that the pairing function and its associated projections, hx; yi 7! x and
y, are computable in polynomial time.
Several functions in this paper are of the form d
Y is D or [0; 1), the set of nonnegative real numbers. Formally, in order
to have uniform criteria for their computational complexities, we regard all
such functions as having domain f0; 1g   , and codomain f0; 1g   if
For example, a function d : N 2 \theta f0; 1g   ! D is formally interpreted as a
function ~
. Under this interpretation, d(i; j; means
that ~
where u is a suitable binary encoding of the dyadic
rational r.
For a function d : N \theta we define the function
xi). We then regard d as a "uniform
enumeration" of the functions d
(n - 2), we write d
For a function for the n-fold
composition of ffi with itself.
Our proof of the Weak Stochasticity Theorem uses the following form of
the Chernoff bound.
Lemma 2.1.[4, 7]. If are independent 0-1-valued random variables
with the uniform distribution,
In particular, taking
Proof. See
3 Measure and Weak Stochasticity
In this section, after reviewing some fundamentals of measure in exponential
time complexity classes, we prove the Weak Stochasticity Theorem. This
theorem will be useful in the proof of our main result in section 4. We also
expect it to be useful in future investigations of the measure structure of E
Resource-bounded measure [15, 16] is a very general theory whose special
cases include classical Lebesgue measure, the measure structure of the class
REC of all recursive languages, and measure in various complexity classes. In
this paper we are interested only in measure in E and E 2 , so our discussion
of measure is specific to these classes. The interested reader may consult
section 3 of [15] for more discussion and examples.
Throughout this section, we identify every language A ' f0; 1g   with its
characteristic sequence -A 2 f0; 1g 1 , defined as in section 2.
A constructor is a function  such that x !
all x 2 f0; 1g   . The result of a constructor ffi (i.e., the language constructed
by ffi) is the unique language R(ffi) such that ffi n (-) v R(ffi) for all n 2 N.
(Recall that this means that each string ffi n (-) is a prefix of the characteristic
sequence of R(ffi).) Intuitively, ffi constructs R(ffi) by starting with - and then
iteratively generating successively longer prefixes of R(ffi). Given a set \Delta of
functions from f0; 1g   into f0; 1g   , we write R(\Delta) for the set of all languages
R(ffi) such that is a constructor.
We first note that the exponential time complexity classes E and E 2 can
be characterized in terms of constructors.
Notation. The classes both consisting of functions f
are defined as follows.
is computable is polynomial timeg
is computable is n (log n) O(1)
timeg
Lemma 3.1.[13]
1.
2.
Using Lemma 3.1, the measure structures of E and E 2 are now developed
in terms of the classes p i , for 2.
Definition. A density function is a function d : f0; 1g   ! [0; 1) satisfying
for all w 2 f0; 1g   . The global value of a density function d is d(-). The set
covered by a density function d is
w2f0;1g
(Recall that xg is the cylinder generated by w.) A
density function d covers a set X ' f0; 1g 1 if X ' S[d].
For all density functions in this paper, equality actually holds in (3.1)
above, but this is not required.
Consider the random experiment in which a sequence x 2 f0; 1g 1 is
chosen by using an independent toss of a fair coin to decide each bit of
x. Taken together, parts (3.1) and (3.2) of the above definition imply that
in this experiment. Intuitively, we regard a density
function d as a "detailed verification" that Pr[x 2 X] - d(-) for all sets
More generally, we will be interested in "uniform systems" of density
functions that are computable within some resource bound.
An n-dimensional density system (n-DS) is a function
such that d ~ k is a density function for every ~ k 2 N n . It is sometimes convenient
to regard a density function as a 0-DS.
A computation of an n-DS d is a function b
such that fi fi fi b
d ~ k;r
(w)
for all ~ k 2 N n , r 2 N, and w 2 f0; 1g   . For -computation of an
n-DS d is a computation b
d of d such that b
if there exists a p i -computation b
d of d.
If d is an n-DS such that d : N n \theta f0; 1g   ! D and d 2 p i , then d
is trivially p i -computable. This fortunate circumstance, in which there is
no need to compute approximations, occurs frequently in practice. (Such
applications typically do involve approximations, but these are "hidden" by
invoking fundamental theorems whose proofs involve approximations.)
We now come to the key idea of resource-bounded measure theory.
Definition. A null cover of a set X ' f0; 1g 1 is a 1-DS d such that, for all
covers X with global value d k (- 2 \Gammak . For
cover of X is a null cover of X that is p i -computable.
In other words, a null cover of X is a uniform system of density functions
that cover X with rapidly vanishing global value. It is easy to show that a
set X ' f0; 1g 1 has classical Lebesgue measure 0 (i.e., probability 0 in the
above coin-tossing experiment) if and only if there exists a null cover of X.
Definition. A set X has p i -measure 0, and we write - p i
there
exists a p i -null cover of X. A set X has p i -measure 1, and we write - p i
Thus a set X has p i -measure 0 if p i provides sufficient computational
resources to compute uniformly good approximations to a system of density
functions that cover X with rapidly vanishing global value.
We now turn to the internal measure structures of
Definition. A set X has measure 0 in R(p i ), and we write -(X j R(p i
set X has measure 1 in R(p i ), and we write
we say that
almost every language in R(p i ) is in X.
The following lemma is obvious but useful.
Lemma 3.2. For every set X ' f0; 1g 1 ,
where the probability Pr[x 2 X] is computed according to the random experiment
in which a sequence x 2 f0; 1g 1 is chosen probabilistically, using
an independent toss of a fair coin to decide each bit of x.
Thus a proof that a set X has p-measure 0 gives information about the
size of X in E, in E 2 , and in f0; 1g 1 .
It was noted in Lemma 3.2 that -p
In fact,
more is true.
Lemma 3.3. [17] Let Z be the union of all sets X such that -p
Lemma 3.3 is also called the Abundance Theorem, because it implies that
almost every language A 2 E 2 is p-random, i.e., has the property that the
singleton set fAg does not have p-measure 0. The proof of Lemma 3.3 makes
essential use of the fact that p 2 contains a universal function for p. It is not
the case that - p
It is shown in [15] that these definitions endow E and E 2 with internal
measure structure. Specifically, for I is either the collection I p i
of all p i -measure 0 sets or the collection I R(p i ) of all sets of measure 0 in
I is a "p i -ideal", i.e., is closed under subsets, finite unions, and
(countable unions that can be generated with the resources of
importantly, the Measure Conservation Theorem of [15] says that
the ideal IR(p i ) is a proper ideal, i.e., that E does not have measure 0 in E
does not have measure 0 in E 2 . Taken together, these facts justify
the intuition that, if negligibly small subset of
(and similarly for
Our proof of the Weak Stochasticity Theorem does not directly use the
above definitions. Instead we use a sufficient condition, proved in [15], for a
set to have measure 0. To state this condition we need a polynomial notion
of convergence for infinite series. All our series here consist of nonnegative
terms. A modulus for a series
a n is a function m
a
for all j 2 N. A series is p-convergent if it has a modulus that is a polynomial.
A sequence 1
a
of series is uniformly p-convergent if there exists a polynomial
such that, for each j 2 N, m j is a modulus for the seriesP
a j;k . We will
use the following sufficient condition for uniform p-convergence. (This well-known
lemma is easily verified by routine calculus.)
Lemma 3.4. Let a j;k 2 [0; 1) for all N. If there exist a real " ? 0 and
a polynomial g : N ! N such that a j;k - e \Gammak "
for all
then the series 1
a
are uniformly p-convergent. 2
The proof of the Weak Stochasticity Theorem is greatly simplified by
using the following special case (for p) of a uniform, resource-bounded generalization
of the classical first Borel-Cantelli lemma.
Lemma 3.5.[15]. If d is a p-computable 2-DS such that the seriesX
are uniformly p-convergent, then
k=t
S[d j;k
k=t
sufficient condition for concluding that S has p-measure 0. Note that each S j
consists of those languages A that are in infinitely many of the sets S[d j;k ].
We now formulate our notion of weak stochasticity. For this we need
a few definitions. Our notion of advice classes is standard [11]. An advice
function is a function h Given a function q
ADV(q) for the set of all advice functions h such that jh(n)j - q(n) for all
Given a language A ' f0; 1g   and an advice function h, we define
the language A=h ("A with advice h") by
Given functions t; N, we define the advice class
Then A is weakly
(t; q; -stochastic if, for all B 2 DTIME(t)=ADV(q) and all C 2 DTIME(t)
such that jC =n j -(n) for all sufficiently large n,
lim
Intuitively, B and C together form a "prediction scheme" in which B
tries to guess the behavior of A on the set C. A is weakly (t; q; -stochastic
if no such scheme is better in the limit than guessing by random tosses of a
fair coin.
Our use of the term "stochastic" follows Kolmogorov's terminology [12,
28] for properties defined in terms of limiting frequencies of failure of prediction
schemes. The adverb "weakly" distinguishes our notion from a stronger
stochasticity property considered in [17], but weak stochasticity is a powerful
and convenient tool.
The following lemma captures the main technical content of the Weak
Stochasticity Theorem.
Lemma 3.6. Fix c 2 N and
Proof. Assume the hypothesis. Let U 2 DTIME(2 (c+1)n ) be a language that
is universal for DTIME(2 cn ) \theta DTIME(2 cn ) in the following sense. For each
Ng.
For all define the set Y i;j;k of languages as follows. If k is not
a power of 2, then Y
z2f0;1g -cn
where each
A ' f0; 1g
and
It is immediate from the definition of weak stochasticity that the complement
c;fl of WS c;fl satisfies
c;fl '[
k=m
It follows by Lemma 3.5 that it suffices to exhibit a p-computable 3-DS d
with the following two properties.
(I) The seriesP
d i;j;k (-), for are uniformly p-convergent.
(II) For all
Define the function d : N 3 \theta f0; 1g   ! [0; 1) as follows. If k is not a
power of 2, then d i;j;k
z2f0;1g -cn
where the conditional probabilities Pr(Y i;j;k;z jCw
are computed according to the random experiment in which the language
A ' f0; 1g   is chosen probabilistically, using an independent toss of a fair
coin to decide membership of each string in A.
It follows immediately from the definition of conditional probability that
d is a 3-DS. Since U 2 DTIME(2 (c+1)n ) and c is fixed, we can use binomial
coefficients to (exactly) compute d i;j;k (w) in time polynomial in i+j+k+jwj.
Thus d is p-computable.
To see that d has property (I), note first that the Chernoff bound, Lemma
2.1, tells us that, for all (writing
whence
d i;j;k
z2f0;1g -cn
Let
l 1
such that
Then g is a polynomial and, for all (writing
- [4 a (j
Thus d i;j;k (-) ! e \Gammak ffi
for all
follows by Lemma 3.4 that (I) holds.
Finally, to see that (II) holds, fix k is not a power of 2, then
(II) is trivially affirmed, so assume that
Fix z 2 f0; 1g -cn such that A 2 Y i;j;k;z and let w be the
characteristic string of A-n . Then
d i;j;k (w) - Pr(Y i;j;k;z jCw
so A 2 Cw ' S[d i;j;k ]. This completes the proof of Lemma 3.6. 2
We now have the main result of this section.
Theorem 3.7 (Weak Stochasticity Theorem).
(1) For all c 2 N and fl ? 0, almost every language A 2 E is weakly
(2) Almost every language A
Proof. Part (1) follows immediately from Lemma 3.6 via Lemma 3.2. Part
(2) follows from Lemma 3.6 via Lemmas 3.3 and 3.2. 2
4 The Density of Hard Languages
In this section we prove our main result, that for every real ff ! 1, the
set P n ff \Gammatt (DENSE c ) has measure 0 in E and in E 2 . We then derive some
consequences of this result. Some terminology and notation will be useful.
Given a query-counting function q q-query function is a
function f with domain f0; 1g   such that, for all x 2 f0; 1g   ,
Each f i (x) is called a query of f on input x. A q-truth table function is a
function g with domain f0; 1g   such that, for each x 2 f0; 1g   , g(x) is the
encoding of a q(jxj)-input, 1-output Boolean circuit. We write g(x)(w) for
the output of this circuit on input w 2 f0; 1g q(jxj) . A - P
q\Gammatt -reduction is an
ordered pair (f; g) such that f is a q-query function, g is a q-truth table
function, and f and g are computable in polynomial time.
q\Gammatt -reduction of A to B is a - P
q\Gammatt -reduction
(f; g) such that, for all x 2 f0; 1g   ,
(Recall that denotes the Boolean value of the condition /.) In this case
we say that
g. We say that A is - P
q\Gammatt -reducible to B, and write
q\Gammatt B, if there exists (f; g) such that A - P
The proof of our main result makes essential use of the following construction

Given an n ff -query function f and n 2 N, the sequentially most frequent
query selection (smfq selection) for f on inputs of length n is the sequence
defined as follows. Each S k ' f0; 1g n . Each Q k is an jS k j \theta n ff matrix of
strings, with each string in Q k colored either green or red. The rows of Q k
are indexed lexicographically by the elements of S k . For x row x of Q k
is the sequence f 1 (x); :::; f n ff (x) of queries of f on input x. If Q k contains at
least one green string, then y k is the green string occurring in the greatest
number of rows of Q k . (Ties are broken lexicographically.) If Q k is entirely
red, then y undefined). The sets S k and the coloring are
specified recursively. We set S and color all strings in Q 0 green.
Assume that S k
then (S is the set of all
such that y k appears in row x of Q k . The strings in Q k+1 are then
colored exactly as they were in Q k , except that all y k 's are now colored red.
This completes the definition of the smfq selection.
For it is clear that every row of Q k contains at least k red
strings. In particular, the matrix Q n ff is entirely red.
Our main results follow from the following lemma. Recall that WS c;fl is
the set of all weakly languages.
Lemma 4.1. For every real ff
Proof. Let assume that A - P
It suffices to show that A 62 WS 3; 1. Fix a polynomial p such that jf i (x)j -
that the following conditions hold for all n - n 0 .
2.
Let
g:
Note that K is infinite because L is not dense.
languages B, C, D and an advice function h
follows. For all
C=n , D=n , and h(n) are defined from the smfq selection for f on inputs of
length n as follows: Let be the greatest integer such that 0 - k - n ff
and
. (Note that k exists because jS We then define
and we let D=n be the set of all coded pairs hx; zi such that x 2 S k , z 2
each
Finally, we let tries to predict A on C. Specif-
ically, for each n - n 0 and each x 2 the bit [[x 2 B]] is a "guessed
value" of the bit [[x 2 A]]. The actual value, given by the reduction (f; g) to
L, is
are the entries in row x of the matrix Q k . The guessed
value uses the advice function h to get the correct
when the string w i is red in Q k , and guesses that w i 62 L
when the string w i is green in Q k .
It is easy to see that C; D 2 DTIME(2 3n
(The bound 3n is generous here.) Also, by condition (i) in our choice of n 0 ,
2 for all n 2 N.
We now show that B does a good job of predicting A on C=n , for all
We have two cases.
strings in Q k are red, so all the guesses made
by B are correct, so
r be the number of rows in Q k , i.e.,
jC =n j. By our choice of k, we have
\Gamman 2ffl
r:
That is, no green string appears in more than 2 \Gamman 2ffl
r of the rows of Q k .
Moreover, since jL -p(n)
, there are at most 2 n ffl
green strings w in
such that w 2 L. Thus there are at most 2 \Gamman 2ffl
\Gamman 2ffl
r rows
of Q k in which B makes an incorrect guess that a green string is not in
L; the guesses made by B are correct in all other rows! By condition
(ii) in our choice of n 0 , then, B is incorrect in at most 1r rows of Q k .
That is,
In either case, (I) or (II), we have
Since this holds for all n 2 K, and since K is infinite,
Thus B and C testify that A is not weakly (2 3n ; 3n; 2 n
)-stochastic, i.e., that
A 62 WS 3; 1. 2
Our main results are now easily derived. We start with the fact that
most languages decidable in exponential time are not - P
-reducible to
non-dense languages.
Theorem 4.2 (Main Theorem). For every real number ff ! 1,
Proof. This follows immediately from Theorem 3.7 and Lemma 4.1. 2
The Main Theorem yields the following separation result.
Theorem 4.3. For every real ff ! 1,
That is, every P n ff \Gammatt -hard language for E is dense.
Proof. By the Measure Conservation Theorem [15], -(E j E) 6= 0, so this
follows immediately from Theorem 4.2. 2
Note that Theorem 4.3 strengthens Theorem 1.2 by extending the number
of queries from O(log n) to n ff , where ff
It is worthwhile to examine the roles played by various methods. Theorem
4.2, a measure-theoretic result concerning the quantitative structure of E and
yields the qualitative separation result Theorem 4.3. From a technical
standpoint, this proof of Theorem 4.3 has the following three components.
(i) The sequentially most frequent query selection (Lemma 4.1). This is
used to prove that every language in P n ff \Gammatt (DENSE c ) is predictable,
i.e., fails to be weakly stochastic (with suitable parameters).
(ii) The Weak Stochasticity Theorem (Theorem 3.7). This shows that only
a measure 0 subset of the languages in E are predictable.
(iii) The Measure Conservation Theorem [15]. This shows that E is not a
measure 0 subset of itself.
Of these three components, (ii) and (iii) are general theorems concerning
measure in E. Only component (i) is specific to the issue of the densities of
languages. That is, given the general principles (ii) and (iii), the
proof of Theorem 4.3 is just the sequentially most frequent query selection,
i.e., the proof of Lemma 4.1. The latter proof is combinatorially much simpler
than Watanabe's direct proof of Theorem 1.2. This is not surprising, once it is
noted that our proof of Theorem 4.3 is an application of (a resource-bounded
generalization of) the probabilistic method [5, 24, 25, 6, 26, 1], which exploits
the fact that it is often easier to establish the abundance of objects of a given
type than to construct a specific object of that type. Much of our proof of
Theorem 4.3 is "hidden" in the power of this method (i.e., in the proofs of
the Measure Conservation and Weak Stochasticity Theorems), freeing us to
apply the sequentially most frequent query selection to the problem at hand.
An important feature of this general method is that it is uniformly constructive
in the following sense. Taken together, the proofs of the Measure
Conservation and Weak Stochasticity Theorems give a straightforward, "au-
tomatic" construction of a language A
follows immediately that A 2 EnP n ff \Gammatt (DENSE c ). Thus one can apply this
complexity-theoretic version of the probabilistic method with complete assurance
that the resulting existence proof will automatically translate into a
construction.
The primary objective of resource-bounded measure theory is to give a
detailed account of the quantitative structure of E, E 2 , and other complexity
classes. The derivation of qualitative separation results, such as Theorems 4.3
and 1.2, is only a by-product of this quantitative objective. (By analogy, the
value of classical Lebesgue measure and probability far surpasses their role
as tools for existence proofs.) In the case of E, for example, the quantitative
content of Theorem 4.2 is that the set P n ff \Gammatt (DENSE c negligibly
small subset of E.
As noted in the introduction to this paper, we are interested in the consequences
of the hypothesis that NP is not a negligibly small subset of exponential
time. In this regard, our main theorem yields the following result.
Theorem 4.4. If -(NPjE) 6= 0 or -(NPjE 2 ) 6= 0, then for all ff ! 1, every
language for NP is dense, i.e., NP 6' P n ff \Gammatt (DENSE c ).
Proof. If NP has a - P
language H that is not dense then Theorem
4.2 tells us that
Note that the hypothesis and conclusion of Theorem 4.4 are both stronger
than their counterparts in Ogiwara and Watanabe's result that
Note also that our proof of Theorem 4.4 actually shows that
In fact, this implication and Theorem 4.4 both hold with NP replaced by
PH, PP, PSPACE, or any other class.
5 Conclusion
The density criterion in Theorem 4.2 cannot be improved, since for every
there is a language A 2 E that is - P
for all n. It is an open question whether the query bound n ff can be
significantly relaxed. A construction of Wilson [31] shows that there is an
oracle B such that
O(n)\Gammatt (SPARSE), so progress in this direction will
require nonrelativizable techniques.
There are several open questions involving special reducibilities. We mention
just one example. Very recently, Arvind, K-obler, and Mundhenk [2] have
proven that
where P ctt refers to polynomial-time conjunctive reducibility. (This strengthens
Theorem 1.4.) Does the class P btt (P ctt (DENSE c )) have measure 0 in E?
As noted in the introduction, all known - P
-hard languages for NP are
dense, i.e., our experience suggests that NP 6' P(DENSE c ). This suggests
two open questions. (See Figure 1.) Karp and Lipton [11] have shown that
Theorem 4.4 of the present paper shows that
for ff ! 1. The first question, posed by Selman [23], is whether the strong
hypothesis -(\Sigma p
can be used to combine these ideas to get a
conclusion that NP 6' P(DENSE c ). The second, more fundamental, question
is suggested by the first. A well-known downward separation principle
[27] says that, if the polynomial time hierarchy separates at some level,
then it separates at all lower levels. Thus, for example, \Sigma p
implies
that P 6= NP. Is there a "downward measure separation principle," stating
that -(\Sigma p
In particular, does
imply that -(NP
The hypothesis that -(NPjE 2 ) 6= 0, i.e., that NP is not a negligibly small
subset of E 2 , has recently been shown to have a number of credible conse-
quences: If -(NPjE 2 ) 6= 0, then NP contains p-random languages [17]; NP
contains E-bi-immune languages [20]; every - P
-hard language for NP has
an exponentially dense, exponentially hard complexity core [9]; and now, by

Figure

1: Insert the MSDH-diagram.ps output here
Theorem 4.3 above, every - P
language for NP (ff ! 1) is exponentially
dense. Further investigation of the consequences and reasonableness
of related strong, measure-theoretic hypotheses is clearly
indicated.

Acknowledgements

The first author thanks Bill Gasarch and Alan Selman for helpful discussions.



--R

The Probabilistic Method
Bounded truth-table and conjunctive reductions to sparse and tally sets
On isomorphism and density of NP and other complete sets
A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations
Some remarks on the theory of graphs
Probabilistic Methods in Combinatorics
A guided tour of Chernoff bounds
How hard are sparse sets?
The complexity and distribution of hard problems
Kolmogorov complexity
Some connections between nonuniform and uniform complexity classes
Algorithms and random- ness
Category and measure in complexity classes
An upward measure separation theorem
Almost everywhere high nonuniform complexity
in preparation.
in preparation.
Circuit size relative to pseudorandom oracles
Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis
Almost every set in exponential time is P-bi-immune
reported in
On polynomial bounded truth-table reducibility of NP sets to sparse sets
personal communication.
A mathematical theory of communication
The synthesis of two-terminal switching circuits
Ten Lectures on the Probabilistic Method
The polynomial-time hierarchy
Can an individual sequence of zeros and ones be random?
On the Structure of Intractable Complexity Classes
time reducibility to a set of small density
Relativized circuit complexity
--TR

--CTR
John M. Hitchcock, MAX3SAT is exponentially hard to approximate if NP has positive dimension, Theoretical Computer Science, v.289 n.1, p.861-869, 23 October 2002
Olivier Powell, A note on measuring in P, Theoretical Computer Science, v.320 n.2-3, p.229-246, June 14, 2004
John M. Hitchcock, The size of SPP, Theoretical Computer Science, v.320 n.2-3, p.495-503, June 14, 2004
dense languages;resource-bounded measure;complexity classes;computational complexity;sparse languages;weak stochasticity;polynomial reductions