The Complexity and Distribution of Hard Problems.
Measure-theoretic aspects of the $\leq^{\rm P}_{\rm m}$-reducibility  structure of the exponential time complexity classes E=DTIME($2^{\rm linear}$) and $E_{2}={\rm DTIME}(2^{\rm polynomial})$ are investigated. Particular attention is given to the complexity (measured  by the size of complexity cores) and distribution  (abundance in the sense of measure) of languages that are $\leq^{\rm P}_{\rm m}$-hard for E and other complexity classes.  Tight upper and lower bounds on the size of complexity cores of hard languages are derived.  The upper bound says that the  $\leq^{\rm P}_{\rm m}$-hard languages for E are unusually simple, in the  sense that they have smaller complexity cores than most  languages in E.  It follows that the $\leq^{\rm P}_{\rm m}$-complete languages for E form a measure 0 subset of E (and similarly in $E_2$).  This latter fact is seen to be a special case of a more general theorem, namely, that {\it every} \pmr-degree (e.g., the degree of all \pmr-complete languages for NP) has measure 0 in E and in \Ep.
Introduction
A decision problem (i.e., language) A ' f0; 1g   is said to be hard for a complexity class C
if every language in C is efficiently reducible to A. If A is also an element of C, then A is
complete for C. The most common interpretation of "efficiently reducible" here is "polynomial
time many-one reducible," abbreviated "- P
-reducible." (See section 2 for notation and
terminology used in this introduction.) For example, in most usages, "NP-complete" means
m -complete for NP," the completeness notion introduced by Karp [15] and Levin [16].
This research was supported in part by National Science Foundation Grants CCR-8809238 and CCR-
9157382, with matching funds from Rockwell International and Microware Systems Corporation, and in part
by the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), where the second
author was a visitor while part of this work was carried out.
In this paper, we investigate the complexity (measured by size of complexity cores) and
distribution (i.e., abundance in the sense of measure) of languages that are - P
(equivalently, classes, including NP. (By "measure" here, we mean
resource-bounded measure as developed by Lutz [17] and described in section 3 of the present
paper.) We give a tight lower bound and, perhaps surprisingly, a tight upper bound on the
sizes of complexity cores of hard languages. More generally, we analyze measure-theoretic
aspects of the - P
-reducibility structure of exponential time complexity classes. We prove
that - P
-hard problems are rare, in the sense that they form a p-measure 0 set. We also
prove that every - P
m -degree has measure 0 in exponential time.
Complexity cores, first introduced by Lynch [24] have been studied extensively [8, 9, 10,
11, 12, 14, 27, 28, 29, etc. Intuitively, a complexity core of a language A is a fixed set
K of inputs such that every machine whose decisions are consistent with A fails to decide
efficiently on all but finitely many elements of K. The meaning of "efficiently" is a parameter
of the definition that varies according to the context. (See section 4 for a precise definition.)
Orponen and Sch-oning [28] have established two lower bounds on the sizes of complexity
cores of hard languages. First, every - P
-hard language for E has a dense P-complexity
core. Second, if P 6= NP, then every - P
-hard language for NP has a non-sparse polynomial
complexity core.
In section 4 below, we extend the first of these results to languages that are weakly - P
hard for E. language A is - P
m -hard for E if every element of E is - P
m -reducible to A. A
language A is weakly - P
m -hard for E if every element of some nonnegligible, i.e., non-measure
0, set of languages in E is reducible to A. Very recently, Lutz [21] has proven that "weakly
m -hard" is more general than "- P
Specifically, we prove that every language that
is weakly - P
m -hard for E or E 2 has a dense exponential complexity core. It follows that, if
NP does not have measure 0 in E or E 2 , then every - P
-hard language for NP has a dense
exponential complexity core. This conclusion is much stronger than Orponen and Sch-oning's
conclusion that every such language has a non-sparse polynomial complexity core, though
it is achieved at the cost of a stronger hypothesis. This hypothesis, originally proposed by
Lutz, is discussed at some length in [20, 22, 23].
In section 5 we investigate the resource-bounded measure of the lower - P
m -spans, the
-spans, and the - P
m -degrees of languages in E and E 2 . (The lower - P
m -span of A
is the set of all languages that are - P
m -reducible to A. The upper - P
m -span of A is the set
of all languages to which A is - P
-reducible. The - P
m -degree of A is the intersection of these
two spans.) We prove the Small Span Theorem, which says that, if A is in E or E 2 , then at
least one of the upper and lower spans must have resource-bounded measure 0. This implies
that every - P
-degree (e.g., the degree of all - P
-complete languages for NP) has measure 0
in E and in E 2 . It also implies that the - P
-hard languages for E form a set of p-measure 0.
As noted in section 7, a proof that is latter fact holds with - P
replaced by - P
would imply
that E 6' BPP.
Languages that are - P
m -hard for E are typically considered to be "at least as complex
as" any element of E. Very early, Berman [6] established limits to this interpretation by
proving that no - P
-complete language is P-immune, even though E contains P-immune
languages. (In fact, Mayordomo [25] has recently shown that almost every language in E
is P-bi-immune.) In section 6 below we prove a very strong limitation on the complexity
of - P
-hard languages for E. We prove that every - P
-hard language for E is decidable in
steps on a dense set of inputs which is also decidable in - 2 4n steps. This implies that
every DTIME(2 4n )-complexity core of every - P
-hard language for E has a dense complement.
Since almost every language in E has f0; 1g   as a DTIME(2 4n )-complexity core (as proven
in section 4), this says that - P
-hard languages for E are unusually simple, in that they have
unusually small complexity cores. Intuitively, we interpret this to mean that the condition
of being - P
m -hard for E forces a language to have a high level of organization, thereby forcing
it to be unusually simple in some respects.
Preliminaries
Here we present the notation and terminology that we use throughout the paper. To begin
with, we write N for the set of natural numbers, Z for the set of integers, and Z + for set of
positive integers.
We deal primarily with strings, languages, functions, and classes. Strings are finite
sequences of characters over the alphabet f0; 1g; we write f0; 1g   for the set of all strings.
Languages are sets of strings. Functions usually map f0; 1g   into f0; 1g   . A class is either a
set of languages or a set of functions.
If x 2 f0; 1g   is a string, we write jxj for the length of x. If A ' f0; 1g   is a language,
then we write A c , A-n , and A=n for f0; 1g   \Gamma A, A " f0; 1g -n , and A " f0; 1g n , respectively.
The sequence of strings over f0; 1g, s is referred to as the
standard enumeration of f0; 1g   .
We use the string-pairing function hx; bd(x)01y, where bd(x) is x with each bit
doubled (e.g., For each
define the function
We say that a property OE(n) of natural numbers holds almost everywhere (a.e.) if OE(n)
is true for all but finitely many n 2 N. Similarly, OE(n) holds infinitely often (i.o.) if OE(n) is
true for infinitely many n 2 N. We write for the Boolean value of a condition OE. That
If A is a finite set, we denote its cardinality by jAj. A language D is dense if there exists
some constant ffl ? 0 such that
a.e. A language S is sparse if there exists a
polynomial p such that jS -n j - p(n) a.e. A language S is co-sparse if S c is sparse.
All machines here are deterministic Turing machines. The language accepted by a machine
M is denoted by L(M ). The partial function computed by a machine M is denoted
by . For a fixed machine M , the function timeM (x) represents the
number of steps that M uses on input x.
If t(n) is a time bound, then we write
for the set of languages decidable in O(t(n)) time. Similarly, we write
for the set of functions computable in O(t(n)-time. The classes of polynomial time decidable
languages and polynomial time computable functions are then
respectively. We are especially interested in classes of languages
decidable in exponential time. We write
and
for the classes of languages decidable in 2 linear time and 2 polynomial time, respectively. Other
complexity classes that we use here, such as NP, PH, PSPACE, etc., have completely standard
definitions [2, 3].
If A and B are languages, then a polynomial time, many-one reduction (briefly - P
reduction) of A to B is a function f 2 PF such that Bg. A
m -reduction of A is a function f 2 PF that is a - P
m -reduction of A to some language B. Note
that f is a - P
m -reduction of A if and only if f is a - P
m -reduction of A to Ag.
We say that A is polynomial time, many-one reducible (briefly, - P
m -reducible) to B, and we
B, if there exists a - P
-reduction f of A to B. In this case, we also say that
A language H is - P
m -hard for a class C of languages if A - P
language
C is - P
m -complete for C if C 2 C and C is - P
m -hard for C. If this is the usual notion
of NP-completeness[13]. In this paper we are especially concerned with languages that are
m -hard or - P
3 Resource-Bounded Measure
Resource-bounded measure [17, 19] 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 [17] 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 by -A N. (Recall from section 2
that s is the standard enumeration of f0; 1g   .) We say that x 2 f0; 1g   is a prefix,
or partial specification, of A ' f0; 1g   if x is a prefix of -A , i.e., if there exists y 2 f0; 1g 1
such that -A = xy. In this case, we write x v A. The set of all languages A for which x is
a partial specification,
is the cylinder specified by the string x 2 f0; 1g   . We say that the measure of the set C x is
2 \Gammajxj . (Note that this is the probability that A 2 C x if A ' f0; 1g   is chosen probabilistically
according to the random experiment in which an independent toss of a fair coin is used to
decide membership of each string x 2 f0; 1g   in A.)
Notation The classes both consisting of functions f are
defined as follows.
is computable in polynomial timeg
is computable in n (log n) O(1) timeg
The measure structures of E and E 2 are 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
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 language A ' f0; 1g   is chosen
by using an independent toss of a fair coin to decide whether each string x 2 f0; 1g   is in A.
Taken together, parts (3.1) and (3.2) of the above definition imply that Pr[A 2
in this experiment. Intuitively, we regard a density function d as a "detailed verification"
that Pr[A 2 X] - d(-) for all sets X ' S[d].
More generally, we are interested in "uniform systems" of density functions that are
computable within some resource bound.
Since density functions are real-valued, their computations must employ finite approximations
of real numbers. For this purpose, let
be the set of dyadic rationals. (These are rational numbers with finite binary expansions.) In
order to have uniform criteria for computational complexity, we consider all functions of the
where each of the sets X, Y is N, f0; 1g   , D, or some Cartesian product
of these sets, to really map f0; 1g   into f0; 1g   . For example, a function f
N \Theta D is formally interpreted as a function ~
. Under this interpretation,
means that ~
are the binary
representations of the integer and fractional parts of q, respectively. Moreover, we only care
about the values of ~
f for arguments of the form h0 and we insist that these values
have the form h0 k ; hu; vii for such arguments.
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 -
D such that
for all ~ k 2 N n , r 2 N, and w 2 f0; 1g   . For -computation of an n-DS d
is a computation -
d of d such that -
-computable if there exists a
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
computable. This fortunate circumstance, in which there is no need to compute approxima-
tions, occurs frequently in practice. (Such applications typically do involve approximations,
but these are "hidden" by invoking fundamental theorems whose proofs involve approxima-
tions).
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 k 2 N, d k covers
X with global value d k (- 2 \Gammak . For of X is a null cover of X that
is
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 - 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 the classes
Definition. A set X has measure 0 in E i , and we write -(X
set X has measure 1 in E i , and we write -(X
we say that almost every language in E i is in X.
We to indicate that X does not have measure 0 in E i . Note that this
does not assert that "-(XjE i )" has some nonzero value.
The following is obvious but useful.
Fact 3.1. For every set X ' f0; 1g 1 ,
where the probability Pr[A 2 X] is computed according to the random experiment in which
a language A ' f0; 1g   is chosen probabilistically, using an independent toss of a fair coin
to decide whether each string x 2 f0; 1g   is in A.
It is shown in [17] 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 E 2 ). The next two results state aspects of this structure that
are especially relevant to the present work.
Theorem 3.2 ([17]). For all cylinders Cw , -(Cw jE) 6= 0 and -(Cw In particular,
The next lemma, which is used in proving Theorem 4.3 and Lemma 5.2, involves the
following computational restriction of the notion of "countable union."
-union of the
Z j and there exists a p i -computable 2-DS d such
that each d j is a p i -null cover of Z j .
Lemma 3.3 ([17]). Let i 2 f1; 2g and let Z; Z If Z is a p i -union of
the
4 Complexity Cores: Lower Bounds
Orponen and Sch-oning [28] have shown that every - P
-hard language for E has a dense
polynomial complexity core. In this section we extend this result by proving that every
weakly - P
-hard language for E has a dense exponential complexity core. We begin by
explaining our terminology.
Given a machine M and an input x 2 f0; 1g   , we write accepts x,
rejects x, and any other case (i.e., if M fails to halt or M halts
without deciding x). If M(x) 2 f0; 1g, we write timeM (x) for the number of steps used in
the computation of M(x). If We partially order the
set f0; 1; ?g by machine M is consistent
with a language A ' f0; 1g   if M(x) -
N be a time bound and let A; K ' f0; 1g   . Then K is a
DTIME(t(n))-complexity core of A if, for every c 2 N and every machine M that is consistent
with A, the "fast set"
our definition of timeM (x), M(x) 2 f0; 1g for all x 2 F . Thus
F is the set of all strings that M "decides efficiently.")
Remark. The above definition quantifies over all machines consistent with A, while the
standard definition of complexity cores (cf. [3]) quantifies only over machines that decide A.
For recursive languages A (and time-constructible bounds t), it is easy to see that the above
definition is exactly equivalent to the standard definition. However, the above definition is
stronger than the standard definition when A is not recursive. For example, consider tally
languages (i.e., languages A ' f0g   ). Under our definition, every DTIME(n)-complexity
core K of every tally language must satisfy 1. However, under the standard
definition, complexity cores are only defined for recursive sets A (as in [3]), or else every
set K ' f0; 1g   is vacuously a complexity core for every nonrecursive language (tally or
otherwise). Thus by quantifying over all machines consistent with A, our definition makes
the notion of complexity core meaningful for nonrecursive languages A. This enables one
to eliminate the extraneous hypothesis that A is recursive from several results. In some
cases, this improvement is of little interest. However in section 6 below, we show that every
-hard language H for E has unusually small complexity cores. This upper bound holds
regardless of whether H is recursive.
Note that every subset of a DTIME(t(n))-complexity core of A is a DTIME(t(n))-
complexity core of A. Note also that, if O(t(n)), then every DTIME(t(n))-complexity
core of A is a DTIME(s(n))-complexity core of A.
1. K is a polynomial complexity core (or, briefly, a P-complexity core) of A if K is a
DTIME(n k )-complexity core of A for all k 2 N.
2. K is an exponential complexity core of A if there is a real number ffl ? 0 such that K
is a DTIME(2 n ffl
)-complexity core of A.
Much of our work here uses languages that are "incompressible by many-one reductions,"
an idea originally exploited by Meyer [26]. The following definitions develop this notion.
Definition. The collision set of a function f : f0; 1g   ! f0; 1g   is
Here, we are using the standard ordering s
Note that f is one-to-one if and only if C
almost everywhere (or, briefly,
one-to-one a.e.) if its collision set C f is finite.
m -reduction of A to B is a
function f 2 DTIMEF(t) such that i.e., such that, for all x 2 f0; 1g   , x 2 A iff
m -reduction of A is a function f that is a - DTIME(t)
m -reduction of A to
f(A).
It is easy to see that f is a - DTIME(t)
m -reduction of A if and only if there exists a language
B such that f is a - DTIME(t)
m -reduction of A to B.
language A ' f0; 1g   is incompressible by - DTIME(t)
reductions if every - DTIME(t)
m -reduction of A is one-to-one a.e. A language A ' f0; 1g
is incompressible by - P
-reductions if it is incompressible by - DTIME(q)
-reductions for all
polynomials q.
Intuitively, if f is a - DTIME(t)
m -reduction of A to B and C f is large, then f compresses
many questions "x 2 A?" to fewer questions "f (x) 2 B?" If A is incompressible by - P
reductions, then very little such compression can occur.
Our first observation, an obvious generalization of a result of Balc'azar and Sch-oning [4]
(see Corollary 4.2 below), relates incompressibility to complexity cores.
Lemma 4.1. If t : N ! N is time constructible, then every language that is incompressible
by - DTIME(t)
m -reductions has f0; 1g   as a DTIME(t)-complexity core.
Proof. Let A be a language that does not have f0; 1g   as a DTIME(t)-complexity core. It
suffices to prove that A is not incompressible by - DTIME(t)
-reductions. This is clear if
or so assume that ; 6= A 6= f0; 1g   . Fix u 2 A and v 2 A c . Since f0; 1g   is
not a DTIME(t)-complexity core of A, there exist c 2 N and a machine M such that M is
consistent with A and the fast set
is infinite. Define a function f : f0; 1g   ! f0; 1g   by
x otherwise.
Since t is time-constructible, f 2 DTIMEF(t). Since M is consistent with A, f is a - DTIME(t)
reduction of A to A. Since F is infinite, at least one of the sets f
so the collision set C f is infinite. Thus A is not incompressible by - DTIME(t)
-reductions. 2
Corollary 4.2. Let c 2 N.
1 (Balcazar and Sch-oning [4]). Every language that is incompressible by - P
-reductions
has f0; 1g   as a P-complexity core.
2. Every language that is incompressible by - DTIME(2 cn )
m -reductions has f0; 1g   as a
3. Every language that is incompressible by - DTIME(2 n c )
m -reductions has f0; 1g   as a
)-complexity core. 2
We now prove that, in E and almost every language is incompressible by - DTIME(t)
reductions, for exponential time bounds t.
Theorem 4.3. Let c 2 Z + and define the sets
incompressible by - DTIME(2 cn )
incompressible by - DTIME(2 n c
almost every language in E is incompressible by - DTIME(2 cn )
reductions, and almost every language in E 2 is incompressible by - DTIME(2 n c
-reductions.
Proof. Let c 2 Z + . We prove that - 1. The proof that - p 2
analogous.
be a function that is universal for DTIMEF(2 cn ), in the sense
that
For each i 2 N, define a set Z i of languages as follows: If the collision set C f i
is finite, then
is infinite, then Z i is the set of all languages A such that f i is a
m -reduction of A.
Define a function d : N \Theta N \Theta f0; 1g   ! [0; 1) as follows: Let
1g.
(i) d i;k
, then d i;k
fix the least j 2 N such that f i
d i;k
It is clear that d is a 2-DS. Since f 2 DTIMEF(2 (c+1)n ) and the computation of d i;k (w) only
uses values f i (u) for strings u with it is also clear that d 2 p, so d is a
p-computable 2-DS.
We now show that Z i ' S[d i;k ] for all
is finite, then this is clear (because
so assume that C f i
is infinite and let A 2 Z i . Let w be a string consisting of the
first l bits of the characteristic sequence of A, where s l\Gamma1 is the k th element of C f i
. This
choice of l ensures that clause (iii) of the definition of d is invoked exactly k times in the
recursive computation of d i;k (w). Since f i is a - DTIME(2 cn )
m -reduction of A (because A 2 Z i ),
we have in each of these k invocations, so
d i;k
Thus A 2 Cw ' S[d i;k ]. This confirms that Z i ' S[d i;k ] for all It follows easily
that, for each i 2 N, d i is a p-null cover of Z i . This implies that
is a p-union of p-measure 0 sets, whence -
Corollary 4.4. Almost every language in E and almost every language in E 2 is incompressible
by - P
-reductions. 2
Corollary 4.5 (Meyer[26]). There is a language A 2 E that is incompressible by - P
reductions. 2
Corollary 4.6. Let c 2 Z + .
1. Almost every language in E has f0; 1g   as a DTIME(2 cn )-complexity core.
2. Almost every language in E 2 has f0; 1g   as a DTIME(2 n c
)-complexity core. 2
We now consider complexity cores of - P
-hard languages. Our starting point is the
following two known facts.
Fact 4.7 (Orponen and Sch-oning [28]). Every language that is - P
m -hard for E (equivalently,
has a dense P-complexity core.
Fact 4.8 (Orponen and Sch-oning [28]). If P 6= NP, then every language that is - P
m -hard for
NP has a nonsparse P-complexity core.
We first extend Fact 4.7. For this we need a definition. The lower - P
m -span of a language
A ' f0; 1g   is
i.e., the set of all languages lying "at or below" A in the - P
-reducibility structure of the set
of all languages. Recall that a language A is - P
m -hard for a complexity class C if C ' Pm (A).
Definition. A language A ' f0; 1g   is weakly - P
m -hard for E (respectively, for
E) language A ' f0; 1g   is weakly
m -complete for E (respectively, for is weakly
Thus a language A is weakly - P
m -hard for E if a nonnegligible subset of the languages in
are - P
m -reducible to A. Very recently, Lutz [21] has established the existence of languages
that are weakly - P
m -complete, but not - P
m -complete, for E (and similarly for Although
m -hard for E" and "- P
m -hard for are equivalent, we do not know the relationship
between "weakly - P
m -hard for E" and "weakly - P
Recall that a language D ' f0; 1g   is dense if there is a real number ffl ? 0 such that
a.e.
Theorem 4.9. Every language that is weakly - P
m -hard for E or E 2 has a dense exponential
complexity core.
Proof. We prove this for E. The proof for E 2 is identical.
Let H be a language that is weakly - P
m -hard for E. Then Pm (H) does not have measure 0
in E, so by Theorem 4.3, there is a language A 2 Pm (H) that is incompressible by -
reductions. Let f be a - P
m -reduction of A to H, let q be a strictly increasing polynomial
bound on the time required to compute f , and let
3\Deltadeg(q) . Then the language
)-complexity core of H.Lutz has proposed the investigation of the consequences of the strong hypotheses
E) 6= 0 and -(NP In this regard, we have the following.
Corollary 4.10. If -(NP j E) 6= 0 or -(NP
-hard language for NP
has a dense exponential complexity core. 2
Thus, for example, if NP is not small, then there is a dense set K of Boolean formulas
in conjunctive normal form such that every machine that is consistent with SAT performs
exponentially badly (either by running for more than 2 jxj ffl
steps or by failing to decide) on
all but finitely many inputs x 2 K.
Note that Theorem 4.9 extends Fact 4.7 and that Corollary 4.10 has a stronger hypothesis
and stronger conclusion than Fact 4.8. Note also that Corollary 4.10 holds with NP replaced
by PH, PP, PSPACE, or any class whatsoever.
The following result shows that the density bounds of Theorem 4.9 and Corollary 4.10
are tight.
Theorem 4.11. For every ffl ? 0, each of the classes NP, E, and E 2 has a - P
language, every P-complexity core K of which satisfies jK-n
a.e.
Proof. Let ffl ? 0, let C be any one of the classes NP, E, E 2 , and let A be a language that is
m -complete for C. Let
ffl e and define the language
Then B is - P
m -complete for C and every P-complexity core K of B satisfies jK-n
a.e.5 Measure of Degrees
In this section we prove that all - P
-degrees have measure 0 in the complexity classes E and
This fact and more follow from the Small Span Theorem, which we prove first.
Recall that the lower - P
m -span of a language A ' f0; 1g   is
Similarly, define the upper - P
m -span of A to be
The - P
m -degree of A is then
deg P
the intersection of the upper and lower spans.
The main result of this section is that, if A is in E or E 2 , then at least one of the spans
(A) is small.
Theorem 5.1.(Small Span Theorem)
1. For every A 2 E,
or
2. For every A 2
or
We first use the following lemma to prove Theorem 5.1 We then prove the lemma.
Lemma 5.2. Let A be a language that is incompressible by - P
-reductions.
1. If A 2 E, then -
2. If A
Proof of Theorem 5.1.
To prove 1, let A 2 E and let X be the set of all languages that are incompressible by
-reductions. We have two cases.
Case I. If us that -(Pm (A) j E) = 0.
Case II. If
Lemma 5.2 tells us that
m (B), it follows that
This proves 1. The proof of 2 is identical. 2 Proof of Lemma 5.2.
To prove 1, let A 2 E be incompressible by - P
-reductions. Let f 2 DTIMEF(2 n ) be a
function that is universal for PF, in the sense that
For each i 2 N, define the set Z i of languages as follows. If the collision set C f i
is infinite,
then
is finite, then
Note that
because A is incompressible by - P
-reductions.
Define a function d : N \Theta N \Theta f0; 1g   ! [0; 1) as follows. Let
1g.
(i) d i;k
(ii) If there is no j - 2jwj such that f i
(iii) If there exists j - 2jwj such that f i then fix the least such j and set
d i;k
It is clear that d is a 2-DS. Also, since f 2 DTIMEF(2 n ) and A 2 E, it is easy to see that
whence d is a p-computable 2-DS.
We now show that Z i ' S[d i;k ] for all infinite, then this is clear (because
so assume that jC f i
be the
string consisting of the first l bits of the characteristic sequence of B, where l is large enough
that
Consider the computation of d i;k (v) by clauses (i), (ii), and (iii) above. Since A - P
via f i , clause (iii) does not cause d i;k (w) to be 0 for any prefix w of v. Let
and
Then clause (iii) doubles the density whenever s jwj 2 T , so
Also, if
Putting this all together, we have
whence This shows that Z i ' S[d i;k ] for all
Since d is p-computable and d i;k
d i is p-null cover of Z i . This implies that P \Gamma1
(A) is a p-union of the p-measure 0 sets Z i . It
follows by Lemma 3.3 that -
This completes the proof of 1.
The proof of 2 is identical. One need only note that, if A
Remark. Ambos-Spies [1] has shown that Pm (A) has Lebesgue measure 0 whenever A 62 P.
Lemma 5.2 obtains a stronger conclusion (resource-bounded measure 0) from a stronger
hypothesis on A.
It is now straightforward to derive consequences of these results for the structure of E
We first note that - P
-hard languages for E are extremely rare.
Theorem 5.3. Let HE be the set of all languages that are - P
m -hard for E. Then -
Proof. Let A be as in Corollary 4.5. Then HE
(A), so Lemma 5.2 tells us that
0:Theorem 5.3 immediately yields an alternate proof of the following result.
Corollary 5.4 (Mayordomo[25]). Let CE , CE 2
be the sets of languages that are - P
for
(Mayordomo's proof of Corollary 5.4 used Berman's result [6], that no - P
language for E is P-immune.)
As it turns out, Corollary 5.4 is only a special case of the following general result. All
-degrees have measure 0 in E and in E 2 .
Theorem 5.5. For all A ' f0; 1g   ,
-(deg P
Proof. Let A ' f0; 1g   . We prove that -(deg P
The proof that -(deg P
0 is identical (in fact simpler, because E 2 is closed under - P
If deg P
holds trivially, so assume that deg P
Then, by Theorem 5.1,
-(deg P
or
-(deg P
We now have the following two corollaries for NP.
Corollary 5.6. Let HNP be the set of languages that are - P
m -hard for NP.
1. If -(NP j E) 6= 0, then -(HNP
2. If -(NP
Proof. This follows immediately from Theorem 5.1, with
Corollary 5.7. Let CNP be the set of languages that are - P
m -complete for NP. Then -(CNP
Proof. Since
m (SAT), this follows immediately from Theorem 5.5. 2
It is interesting to note that Corollary 5.7, unlike Corollary 5.6, is an absolute result,
requiring no unproven hypothesis. The price we pay for this is that we do not know why it
holds! For example, the Small Span Theorem tells us that
in E because -(HNP j E) = 0 or -(NP j E) = 0, but it does not tell us which of these two
very different situations occurs.
Note that Corollaries 5.6 and 5.7 also hold with NP replaced by any other class whatsoever

We conclude this section by noting two respects in which the Small Span Theorem cannot
be improved. First, the hypotheses A 2 E and A 2 E 2 are essential for parts 1 and 2,
respectively. For example, if A is p-random [18], then - p (fAg) 6= 0, so none of deg P
The second respect in which the Small Span Theorem cannot be improved involves the
variety of small-span configurations. In both E and E 2 , either one or both of the upper and
lower spans of a language can in fact be small. We give examples for E.
(a) It is well known [26] that there is a language A 2 E that is both sparse and incompressible
by - P
-reductions. Fix such a language A. By Lemma 5.2, -
Also, since A is sparse, the main result of [22] implies that - p (Pm
(b) If A 2
E) 6= 0.
(c) If A is - P
m -complete for E, then -(P \Gamma1
Theorem 5.3, but
E) 6= 0.
Similar examples can be given for
6 Complexity Cores: Upper Bound
In this section we give an explicit upper bound on the sizes of complexity cores of languages
that are - P
m -hard for E. This bound implies that - P
-complete languages for E have unusually
small complexity cores, for languages in E.
Theorem 6.1. For every - P
-hard language H for E, there exist B;D 2 DTIME(2 4n ) such
that D is dense and
Proof. By Corollary 4.5, there is a language in E that is incompressible by - P
-reductions.
In fact, Meyer's construction [26] shows that there is a language A 2 DTIME(5 n ) that is
incompressible by - P
-reductions. As in Fact 4.7 and Theorem 4.9, this idea has often been
used to establish lower bounds on the complexities of - P
languages. Here we use it to
establish an upper bound.
The following simple notation is useful here. The nonreduced image of a language S '
f0; 1g   under a function f : f0; 1g   ! f0; 1g   is
Note that
for all f and S.
Let H be - P
m -hard for E. Then there is a - P
-reduction f of A to H. Let
it is clear that B;D 2
Fix a polynomial q and a real number ffl ? 0 such that jf(x)j - q(jxj) for all x 2 f0; 1g
and q(n 2ffl
x
. Then, for all sufficiently large n 2 N,
writing we have
whence
for all sufficiently large n. Thus D is dense.
Finally, note that This completes
the proof of Theorem 6.1.
We now use Theorem 6.1 to prove our upper bound on the size of complexity cores for
hard languages.
Theorem 6.2. Every DTIME(2 4n )-complexity core of every - P
-hard language for E has a
dense complement.
Proof. Let H be - P
m -hard for E and let K be a DTIME(2 4n )-complexity core of H. Choose
B;D for H as in Theorem 6.1. Fix machines MB and MD that decide B and D, respectively,
with timeMB be a machine that implements
the following algorithm.
begin
input x;
if MD (x) accepts
then simulate MB (x)
else run forever
so M is consistent with H. Also, there is a constant c 2 N such that for all x 2 D,
Since K is a DTIME(2 4n )-complexity core of H, it follows that K " D is finite. But D is
dense, so this implies that D \Gamma K is dense, whence K c is dense. 2
Note that Theorem 5.3 follows from Corollary 4.6 and Theorem 6.2, but that Theorem
6.2 tells us more.
The main construction of [21] shows that, for every c 2 N, there is a language H that is
weakly - P
m -hard for E and has f0; 1g   as a DTIME(2 cn )-complexity core. Thus, in contrast
with the lower bound given by Theorem 4.9, the upper bound given by Theorem 6.2 cannot
be extended to weakly - P
languages.
Finally, we note that the upper bound given by Theorem 6.2 is tight.
Theorem 6.3. Let c 2 N and 0
1. E has a - P
-complete language with a DTIME(2 cn )-complexity core K that satisfies
a.e.
2. E 2 has a - P
-complete language with a DTIME(2 n c
)-complexity core K that satisfies
a.e.
Proof. We prove the result for E. The proof for E 2 is similar.
Let A be a language that is - P
e. By Corollary 4.6, fix a
language that has f0; 1g   as a DTIME(2 cn )-complexity core. Let
and define the languages
and
It is clear that C is - P
m -complete for E. Also, for all sufficiently large n,
so
a.e.
We complete the proof by showing that K is a DTIME(2 cn )-complexity core for C. For
this, let s 2 N, let M be a machine that is consistent with C, and define the fast set
It suffices to prove that jK "
M be a machine (designed in the obvious way) such that, for all y 2 f0; 1g   ,
M(y) if y 62 D
M is consistent with and M is consistent with C) and
f0; 1g   is a DTIME(2 cn )-complexity core for B, so the fast set
ag
is finite. Since K "
F is finite, it follows that jK "
completing the proof. 2
7 Conclusion
In this paper we have investigated measure-theoretic aspects of the - P
-reducibility structure
of the exponential time complexity classes E and E 2 . Among other things, we have proven
the following. (For simplicity we only consider the class E.)
(i) Every weakly - P
-hard language for E has a dense exponential complexity core (The-
orem 4.9).
(ii) For every language A 2 E, at least one of the spans Pm (A), P
m (A) has resource-bounded
(Theorem 5.1, the Small Span Theorem). Thus the - P
languages for E form a p-measure 0 set (Theorem 5.3), every - P
m -degree has measure
(Theorem 5.5), and the - P
-complete languages for NP form a set of measure 0
in E (Corollary 5.7).
(iii) Every DTIME(2 4n )-complexity core of every - P
-hard language for E has a dense complement
(Theorem 6.2). Since almost every language in E has f0; 1g   as a DTIME(2 4n )-
complexity core (Corollary 4.6), this says that, in E, the - P
-complete languages are
unusually simple, in the sense that they have unusually small complexity cores.
It is reasonable to conjecture that most of our results hold with - P
replaced by - P
T , but
investigating this may be difficult. For example, consider Theorem 5.3. Bennett and Gill [5]
have shown that P \Gamma1
T (A) has (classical) measure 1 for all A 2 BPP. Thus we cannot prove
that the - P
-hard languages for E form a measure 0 set without also proving that E 6' BPP.



--R


Structural Complexity I.
Structural Complexity II.

Relative to a random oracle A
On the structure of complete sets: Almost everywhere complexity and infinitely often speedup.
On isomorphism and density of NP and other complete sets.
The existence and density of generalized complexity cores.

Generalized complexity cores and levelability of intractable sets.
On inefficient special cases of NP-complete problems
Hard core theorems for complexity classes.
Computers and Intractability: A Guide to the Theory of NP-completeness
On solving hard problems by polynomial-size circuits
Reducibility among combinatorial problems.
Universal sequential search problems.
Almost everywhere high nonuniform complexity.
Intrinsically pseudorandom sequences

The quantitative structure of exponential time.
Weakly hard problems.

Cook versus Karp-Levin: Separating completeness notions if NP is not small
On reducibility to complex or sparse sets.
Almost every set in exponential time is P-bi-immune
reported in
A classification of complexity core lattices.
The density and complexity of polynomial cores for intractable sets.

--TR

--CTR
Olivier Powell, A note on measuring in P, Theoretical Computer Science, v.320 n.2-3, p.229-246, June 14, 2004
Klaus Ambos-Spies , Wolfgang Merkle , Jan Reimann , Sebastiaan A. Terwijn, Almost complete sets, Theoretical Computer Science, v.306 n.1-3, p.177-194, 5 September
John M. Hitchcock, The size of SPP, Theoretical Computer Science, v.320 n.2-3, p.495-503, June 14, 2004
Christian Glaer , Mitsunori Ogihara , A. Pavan , Alan L. Selman , Liyu Zhang, Autoreducibility, mitoticity, and immunity, Journal of Computer and System Sciences, v.73 n.5, p.735-754, August, 2007
Lane A. Hemaspaandra, SIGACT news complexity theory column 48, ACM SIGACT News, v.36 n.3, September 2005
resource-bounded measure;polynomial reducibilities;complexity classes;complexitycores;computational complexity;complete problems