Weakly Hard Problems.
A weak completeness phenomenon is investigated in the complexity class ${\rm E}= {\rm DTIME}(2^{\rm linear})$.  According to  standard terminology, a language $H$ is $\leq^{\rm P}_{m}$-hard for E if the set ${\rm P}_{m}(H)$, consisting of all languages $A \leq^{\rm P}_{m}H$, contains the entire class E.  A language $C$ is $\leq^{\rm P}_{m}$-complete for E if it is $\leq^{\rm P}_{m}$-hard for E and is also an element of E.  Generalizing this, a language $H$ is weakly $\leq^{\rm P}_{m}$-hard for E if the set ${\rm P}_{m}(H)$ does not have measure 0 in E.  A language $C$ is weakly $\leq^{\rm P}_{m}$-complete for E if it is weakly $\leq^{\rm P}_{m}$-hard for E and is also an element of E.  The main result of this paper is the construction of a language that is weakly $\leq^{\rm P}_{m}$-complete, but not $\leq^{\rm P}_{m}$-complete, for E. The existence of such languages implies that previously known strong lower bounds on the complexity of weakly $\leq^{\rm P}_{m}$-hard problems for E (given by work of Lutz, Mayordomo, and Juedes) are indeed more general than the corresponding bounds for $\leq^{\rm P}_{m}$-hard problems for E.  The proof of this result introduces a new diagonalization method, called martingale diagonalization.  Using this method, one simultaneously develops an infinite family of polynomial time computable martingales (betting strategies) and a corresponding family of languages that defeat these martingales (prevent them from winning too much money) while also pursuing another agenda.  Martingale diagonalization may be useful for a variety of applications.
Introduction
In practice to date, proving that a decision problem (i.e., language) H '
f0; 1g   is computationally intractable usually amounts to proving that every
member of the complexity class linear )-or some larger class-
is efficiently reducible to H. (See [25] for a survey of such arguments.) For
example, some problems involving the existence of winning strategies for
certain two-person combinatorial games are known to be intractable because
they are polynomial time many-one hard (in fact, logarithmic space many-one
Briefly, a language H is polynomial time many-one hard (abbreviated - P
hard) for E if every language A 2 E is polynomial time many-one reducible
to H (abbreviated A - P
H). A language C is - P
and C is - P
m -hard for E.
A language H that is - P
m -hard for E is clearly intractable in the sense
that
H is not decidable in polynomial time. This is because
a well-known diagonalization argument [3] shows that there is a language
must be the case that B - P
follows that
P.
In fact, languages that are - P
m -hard for E are known to have much
stronger intractability properties. Three examples follow.
Meyer [15] has shown that every - P
-hard language H for E is dense.
This means that there is a real number " ? 0 such that, for all sufficiently
large n, H contains at least 2
strings x 2 f0; 1g -n .
Sch-oning [23] and Huynh [6] have shown that every - P
-hard language
H for E is hard to approximate in the sense that, for every language
A 2 P, the symmetric difference A 4 H is dense. (Note that this
immediately implies result (A) above.)
(C) Orponen and Sch-oning [16] have shown that every - P
-hard language
H for E has a dense polynomial complexity core K. This condition,
defined precisely in section 2 below, means roughly that K is dense and
that every Turing machine that is consistent with H performs badly
(either by running for more than polynomially many steps or by failing
to decide) on all but finitely many inputs x 2 K.
In fact, the proofs of results (A), (B), and (C) all have the same overall
structure as the proof that no - P
-hard language H for E is in P. In each
case, a "very intractable" language exhibited by diagonalization.
This intractability of B, together with the fact that B - P
H, is then shown
to imply the appropriate intractability property for H.
At this time, it appears likely that most interesting intractable problems
are not - P
m -hard for E or larger classes. Insofar as this is true, results such
as (A), (B), and (C) above fail to have interesting cases. Lutz [9] proposed
to remedy this limitation by weakening the requirement that H be - P
for E in such results.
To be more specific, given a language H, the - P
m -span of H (also called
the lower - P
m -span of H [7]) is the set
Pm
A ' f0; 1g
consisting of all languages that are polynomial time many-one reducible to
H. The language H is - P
if Pm (H) contains
all of the complexity class E. Lutz [9] proposed consideration of weaker
hypotheses, stating only that Pm (H) contains a non-negligible subset of E.
The expression "non-negligible subset of E" can be assigned two useful
meanings, one in terms of resource-bounded category [9] and the other in
terms of resource-bounded measure [10, 8]. (Caution: Resource-bounded
measure was incorrectly formulated in [9]. The present paper refers only
to the corrected formulation, in terms of martingales, presented in [10, 8]
and discussed briefly in section 3 below.) Resource-bounded category, a
complexity-theoretic generalization of classical Baire category [17], led to an
extension of result (B) above in [9]. Work since [9] has focused instead on
resource-bounded measure.
Resource-bounded measure is a generalization of classical Lebesgue measure
[2, 18, 17]. As such, it has Lebesgue measure as a special case, but other
special cases provide internal measures for various complexity classes. This
paper concerns the special case of measure in the complexity class E. In par-
ticular, resource-bounded measure defines precisely what it means for a set X
of languages to have measure 0 in E. This condition, written -(X j E) = 0,
means intuitively that negligibly small subset of E. (This intuition
is justified technically in [10] and in section 3 below.) A set Y of languages
has measure 1 in E, written -(Y
the complement of Y . In this latter case, Y is said to contain almost every
language in E.
It is emphasized here that not every set X of languages has a measure
("is measurable") in E. In particular, the expression "-(X j E) 6= 0" only
means that X does not have measure 0 in E. It does not necessarily imply
that X has some other measure in E.
Generalizing the notion of - P
-hardness for E, say that a language H is
weakly - P
E) 6= 0, i.e., if Pm (H) does not have
measure 0 in E. Similarly, say that a language C is weakly - P
m -complete for
m -hard for E. Since E does not have measure 0
in E [10], it is clear that every - P
-hard language for E is weakly - P
m -hard for
E, and hence that every - P
-complete language for E is weakly - P
for E.
The following extensions of results (A), (B), and (C) above are now
known.
have shown that every weakly - P
-hard language
language for E, for ff ! 1) is
dense.
The method of [11] extends in a straightforward matter to show that,
for every weakly - P
-hard language H for E and every language A 2 P,
the symmetric difference A4H is dense.
have shown that every weakly - P
-hard language
H for E has a dense exponential complexity core K. (This condition,
defined in section 2, implies immediately that K is a dense polynomial
complexity core of H.)
extend the strong intractability results (A),
(B), and (C) from - P
-hard languages for E to weakly - P
-hard languages for
This extends the class of problems to which well-understood lower bound
techniques can be applied, unless every weakly - P
-hard language for E is
m -hard for E. Surprisingly, although
-hardness appears to
be a weaker hypothesis than - P
m -hardness, this has not been proven to date.
The present paper remedies this situation. In fact, the Main Theorem, in
section 4 below, says that there exist languages that are weakly - P
but not - P
m -complete, for E. It follows that results
indeed extend the class of problems for which strong intractability results
can be proven.
The Main Theorem is proven by means of a new diagonalization method,
called martingale diagonalization. This method involves the simultaneous
construction, by a mutual recursion, of (i) an infinite sequence of polynomial
time computable martingales (betting strategies); and (ii) a corresponding
sequence of languages that defeat these martingales (prevent them from winning
too much money), while also pursuing another agenda. The interplay
between these two constructions ensures that the sequence of languages in
(ii) can be used to construct a language that is weakly - P
m -complete, but not
m -complete for E. Martingale diagonalization may turn out to be useful
for a variety of applications.
The proof of the Main Theorem also makes essential use of a recent theorem
of Juedes and Lutz [7], which gives a nontrivial upper bound on the
complexities of - P
-hard languages for E.
Section 2 presents basic notation and definitions. Section 3 provides definitions
and basic properties of feasible (polynomial time computable) mar-
tingales, uses these to define measure in E, and proves a new result, the Rigid
Enumeration Theorem. This result provides a uniform enumeration of feasible
martingales that is crucial for the martingale diagonalization method.
Section 4 is devoted entirely to the Main Theorem and its proof. Section 5
briefly discusses directions for future work, with particular emphasis on the
search for natural problems that are weakly - P
m -hard for E.
Preliminaries
All languages (synonymously, decision problems) in this paper are sets of
binary strings, i.e., sets A ' f0; 1g   .
The standard enumeration of f0; 1g   is the infinite sequence
in which strings appear first in order of length, then in lexicographic or-
der. The symbol - denotes the empty string and the expression jwj denotes
the length of a string w 2 f0; 1g   . It is convenient to write the standard
enumeration in the form
That is, for each n 2 N, n is the n th string (counting from 0) in the standard
enumeration of f0; 1g   . Thus,
that jnj denotes the length of the n th string in f0; 1g   .
The Boolean value of a condition / is
ae 1 if / is true
if / is false.
Each language A ' f0; 1g   is identified with its characteristic sequence, which
is the infinite binary sequence
The expression -A denotes the string consisting of the first n bits
of -A .
This paper uses the standard pairing function
\Gamma! onto
defined by
for all k; n 2 N. This pairing function induces the pairing function
\Gamma! onto
defined in the obvious way, i.e., hk; ni is the hk; ni th string in the standard
enumeration of f0; 1g   . Note that jhk; nij - 2(jkj
As noted in section 1, a language A ' f0; 1g   is dense if there is a real
sufficiently large n, A contains at least 2
strings x 2 f0; 1g -n .
Given a function t N, the complexity class DTIME(t(n)) consists
of every language A ' f0; 1g   such that [[x 2 A]] is computable (by a deterministic
Turing machine) in O(t(jxj)) steps. Similarly, the complexity class
consists of every function f : f0; 1g   ! f0; 1g   such that f(x)
is computable in O(t(jxj)) steps. The complexity classes
are of particular interest in this paper.
A language A is polynomial time many-one reducible to a language B,
B, if there is a function f 2 PF such that
for all x 2 f0; 1g   , x 2 A () f(x) 2 B.
Complexity cores, first introduced by Lynch [13], have been studied ex-
tensively. The rest of this section specifies the notions of complexity cores
mentioned in section 1.
Given a (deterministic Turing) machine M and an input x 2 f0; 1g   ,
accepts x
rejects x
? in any other case.
If M(x) 2 f0; 1g, then timeM (x) denotes the number of steps used in the
computation of M(x). If machine M is
consistent with a language A if 1g.
!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"
has finite intersection with K. (By the 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.")
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
every DTIME(t(n))-complexity core of A is a DTIME(s(n))-complexity core
of A.
1. K is a polynomial 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.
Intuitively, a P-complexity core of A is a set of infeasible instances of A,
while an exponential complexity core of A is a set of extremely hard instances
of A.
3 Feasible Martingales
This section presents some basic properties of martingales (betting strate-
gies) that are computable in polynomial time. Such martingales are used to
develop a fragment of resource-bounded measure that is sufficient for understanding
the notion of weakly hard problems. This section also proves the
Rigid Enumeration Theorem, which is crucial for the martingale diagonalization
method used to prove the Main Theorem in section 4.
A martingale is a function d : f0; 1g   ! [0; 1) with the property
that, for all w 2 f0; 1g   ,
A martingale d succeeds on a language A ' f0; 1g   if
lim sup
(Recall that -A [0::n \Gamma 1] is the string consisting of the first n bits of the
characteristic sequence of A.) Finally, for each martingale d, define the set
d succeeds on Ag :
Intuitively, a martingale d is a betting strategy that, given a language A,
starts with capital (amount of money) d(-) and bets on the membership or
nonmembership of the successive strings 0; enumeration
of f0; 1g   ) in A. Prior to betting on a string n, the strategy has capital
d(w), where
After betting on the string n, the strategy has capital d(wb), where
A]]. Condition (3.1) ensures that the betting is fair. The strategy succeeds
on A if its capital is unbounded as the betting progresses.
Example 3.1. by the following recursion. Let
1g.
(See

Figure

1.) It is easily checked that d is a martingale that succeeds on
the language is primeg and on no other language.
Example 3.2. by the following recursion. Let
(See

Figure

2.) It is obvious that d is a martingale that succeeds on every
finite language A. In fact, it is easily checked that S 1 [d] contains exactly
every language A for which the quantity
log 3
is unbounded as denotes the number of 0's in the
string w.
Martingales were used extensively by Schnorr [19, 20, 21, 22] in his investigation
of random and pseudorandom sequences. Lutz [10, 8] used martingales
that are computable in polynomial time to characterize sets that have
measure 0 in E.
Since martingales are real-valued, their computations must employ finite
approximations of real numbers. For this purpose, let
\Gamman

Figure

1: The martingale d of Example 3.1
be the set of nonnegative dyadic rationals. These are nonnegative rational
numbers with finite binary expansions.
Definition. 1. A computation of a martingale d is a function b
f0; 1g   ! D such that fi fi fi b
for all r 2 N and w 2 f0; 1g   satisfying r - jwj, where b
d r
2. A strong computation of a martingale d is a computation b
d of d that
satisfies (3.2) for all r 2 N and w 2 f0; 1g   .
Figure

2: The martingale d of Example 3.2
3. A computation b
d of a martingale d is rigid if it has the following two
properties.
(a) For each r 2 N, the function b
d r is a martingale.
(b) For all r 2 N and w 2 f0; 1g   , if r - jwj, then
d r+1 (w)
4. A p-computation of a martingale d is a computation b
d of d such that
d r (w) is computable in time polynomial in r
5. A p-martingale is a martingale that has a p-computation.
A martingale is here considered to be "feasible" if and only if it is a
p-martingale, i.e., if and only if it has a p-computation. Intuitively, one
might prefer to insist that "feasible" martingales have strong p-computations,
thereby avoiding the ad hoc condition r - jwj. On the other hand, in the
technical arguments of this paper, it is useful to have rigid p-computations,
for reasons explained below. Fortunately, the following lemma shows that all
three of these conditions are equivalent.
Lemma 3.3 (Rigid Computation Lemma). For a martingale d, the following
three conditions are equivalent.
(1) d has a p-computation.
(2) d has a strong p-computation.
(3) d has a rigid p-computation.
Proof. It is trivial that (3) implies (1). To see that (1) implies (2), let b
d be
a p-computation of d. Then the function e
defined by
e
d r
d r+jwj (w) is easily seen to be a strong p-computation of d, so (2)
holds.
To see that (2) implies (3), let b
d be a strong p-computation of d. Define
a function e
by the following recursion. Assume that
d r
d 2r+2 (-).
d r
d 2r+2 (wb)\Gamma b d 2r+2 (wb):
It suffices to show that e
d is a rigid p-computation of d.
It is first shown, by induction on w, that
holds for all r 2 N and w 2 f0; 1g   . For immediately
from the facts that e
d r
d 2r+2 (-) and b
d is a p-computation of d. For the
induction step, assume that (3.3) holds. Then, for b 2 f0; 1g,
e
d
d 2r+2 (wb)\Gamma d(wb)
d
d 2r+2 (wb)\Gamma d(wb)
d
d 2r+2 (wb)\Gamma d(wb)
d
d 2r+2 (wb)fi fi fi fi fi
d
d
(The last inequality holds by the induction hypothesis and the fact that b
d is
a strong p-computation of d.) This confirms that (3.3) holds for all r 2 N
and w 2 f0; 1g   .
Now let r 2 N and w 2 f0; 1g   be such that r - jwj. Then, by (3.3),
This shows that e
d is a computation of d. In fact, since b
d is a p-computation,
it is easily checked that e
d is a p-computation of d. The fact that e
d is rigid
follows from the following two observations.
(a) For each r 2 N, the function e
d r is clearly a martingale by clause (ii) in
the definition of e
d.
(b) For all r 2 N and w 2 f0; 1g   , by (3.4),
d r+1 (w)
Thus (3) holds. 2
Note that the above proof does not construct a p-computation of d that
is both strong and rigid. In fact, it seems reasonable to conjecture that there
exists a p-martingale d for which no p-computation is both strong and rigid.
Note that a function b
D is a rigid computation of some
martingale d if and only if it satisfies the predicates
d) j
d k;r+1 (w)
and
d) j
d r (w1)#
for all r 2 N and w 2 f0; 1g   . The next theorem exploits this fact to
give a very useful enumeration of all p-martingales. The following definition
specifies the useful properties of this enumeration.
Definition. A rigid enumeration d
consists of a sequence d sequence b
with the following
properties.
is an enumeration of all p-martingales.
(ii) For each k 2 N, b
d k is a rigid p-computation of d k .
(iii) There is an algorithm that, given k; r 2 N and w 2 f0; 1g   , computes
d k;r (w) in at most (2 steps.
The following theorem is the main result of this section.
Theorem 3.4 (Rigid Enumeration Theorem). There exists a rigid enumeration
of all p-martingales.
Proof. Fix a function e g : N 2 \Theta f0; 1g   ! D with the following properties.
(Write e
is an enumeration of all functions f
that f(r; w) is computable in time polynomial in r
(ii) There is an algorithm that, given k; r 2 N and w 2 f0; 1g   , computes
e
k;r (w) in at most (2 steps.
(The existence of such an efficient universal function is well-known [3, 4].)
Most of this proof is devoted to two claims and their respective proofs.
The first of these claims is the following.
Claim 1. There is a function b
with the following
properties. (Write b g k;r
(a) For each k 2 N, b
k is a rigid p-computation of some martingale g k .
(b) For each k 2 N, if e
k is already a rigid p-computation of some martingale
k .
(c) There is a constant c 2 N such that, for all k; r 2 N and w 2 f0; 1g   ,
k;r (w) is computable in at most (2 steps.
Assume for the moment that Claim 1 is true. Define functions b
d k;r
is not of this form,
d k;r (w):
The second claim is the following.
2. The sequences d
constitute a rigid enumeration
of all p-martingales.
To prove Claim 2 (still assuming Claim 1), first note that, for all k 2 N
and w 2 f0; 1g   ,
ae
is not of this form.
By part (a) of Claim 1, this immediately implies that each d k is a p-martingale.
Conversely, assume that d 0 : f0; 1g   ! [0; 1) is a p-martingale. Then, by
the Rigid Computation Lemma and clause (i) in the specification of e
g, there
is some j 2 N such that e g j is a rigid p-computation of d 0 . Choose k 2 N
such that
j by part (b) of Claim 1, so e
d k is a rigid
p-computation of d 0 , so d This shows that d 0 is an enumeration
of all p-martingales and that each b
d k is a rigid p-computation of d k . For
required to compute b
d k;r (w) satisfies
This prove Claim 2, and hence the theorem. All that remains, then, is to
prove Claim 1.
To prove Claim 1, the values b
k;r (w) are first specified for all k; r 2 N and
. Define the following predicates. (In these predicates, it is useful
to regard k; r 2 N and w 2 f0; 1g   as parameters and f; b
as variables.)
ff k;r;w (f; b
by recursion on r and w as follows. Let k; r 2 N,
1g.
k;r (-) otherwise
e
g) and
g) and
k;r (w) otherwise
By condition (ii) in the choice of e
g, the function b
defined by this recursion
is easily seen to satisfy condition (c) of Claim 1.
To see that b
satisfies condition (a) of Claim 1, let k 2 N be arbitrary.
A routine induction on r shows that fi k;r;w (e holds for all r 2 N and w 2
f0; 1g   . It follows easily that each b
k;r is a martingale. A routine induction
on w then shows that ff k;r;w (e
g) holds for all r 2 N and w 2 f0; 1g   .
It follows that b g k is a rigid p-computation of the martingale g k defined by
k;r (w). Thus b
satisfies condition (a) of Claim 1.
Finally, to see that b g satisfies condition (b) of Claim 1, fix k 2 N and
assume that e g k is a rigid computation of some martingale g k . Then a routine
induction on r and w shows that b
k . (The ff and fi predicates hold
throughout the induction, so the "otherwise" cases are never invoked in the
definition of b
k .) This completes the proof of Claim 1 and the proof of the
Rigid Enumeration Theorem. 2
The rest of this section briefly develops those aspects of measure in E
that are used in this paper. The key ideas are in the following definition.
Definition. 1. A set X of languages has p-measure 0, written -
there is a p-martingale d such that X ' S 1 [d].
2. A set X of languages has measure 0 in E, written -(X j E) = 0, if
3. A set X of languages has measure 1 in E, written -(X j E) = 1, if
is the complement of X. In this case, X is said to
contain almost every language in E.
4. The expression -(X j E) 6= 0 indicates that X does not have measure
in E. Note that this does not assert that "-(X j E)" has some nonzero
value.
Thus, a set X of languages has measure 0 in E if there is a feasible
martingale that succeeds on every element of X.
The following fact is obvious but useful.
Proposition 3.5. Every set X of languages satisfies the implications
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.
The right-hand implication in Proposition 3.5 makes it clear that p-
measure 0 sets are negligibly small. What is significant for complexity theory
is that, if X has measure 0 in E, then negligibly small as a subset
of E. This intuition is technically justified in [10], where it is shown that
finite subsets of E have measure 0 in E, and that the sets of measure 0 in E
are closed under subset, finite unions, and certain countable unions, called
"p-unions." Most importantly, the following is shown.
Theorem 3.6 [10]. -(E j E) 6= 0.
Combined with the above-mentioned closure properties, this result (which
is a special case of the more general Measure Conservation Theorem [10])
ensures that in a nontrivial sense, a negligibly small subset of E
whenever X has measure 0 in E.
4 Weak Completeness in E
In standard terminology, a language H is - P
m -hard for a complexity class C
if the set
Pm
A
contains all of C. A language C is - P
m -complete for C if C 2 C and C is
m -hard for C. The following definition generalizes these notions for the
complexity class
language H is weakly - P
E) 6= 0,
i.e., the set Pm (H) does not have measure 0 in E. A language C is weakly
m -hard for E.
By Theorem 3.6, every - P
-hard language for E is weakly - P
m -hard for E,
whence every - P
-comlete language for E is weakly - P
m -complete for E. The
following result says that the converse does not hold, i.e., that in E, weak
m -completeness is a proper generalization of - P
-completeness.
Theorem 4.1 (Main Theorem). There is a language C that is weakly
m -complete, but not - P
m -complete, for E.
The rest of this section is devoted to proving the Main Theorem.
A recent theorem of Juedes and Lutz gives a necessary condition for a
language to be - P
m -hard for E. This condition, based on an idea of Meyer [15],
plays an important role in the present proof. The key ideas are developed in
the following definitions.
Definition. The collision set of a function f : f0; 1g   ! f0; 1g   is
A function f : f0; 1g   ! f0; 1g   is one-to-one almost everywhere if C f is
finite.
many-one reduction of A is a
computable function f : f0; 1g   ! f0; 1g   such that
that, for all x 2 f0; 1g   , f(x) 2 f(A) implies x 2 A. A - DTIME(t)
-reduction
of A is a many-one reduction f of A such that f 2 DTIMEF(t).
N. Then A is incompressible by
-reductions if every - DTIME(t)
m -reduction of A is one-to-one almost
everywhere.
Intuitively, if f is a - DTIME(t)
m -reduction of A and C f is large, then f
many questions "x 2 A?" to fewer questions "f (x) 2 f(A)?" If
A is incompressible by - DTIME(t)
-reductions, then A is "very complex" in the
sense that very little such compression can occur.
The following result is used here.
Theorem 4.2 (Juedes and Lutz [7]). No language that is - P
m -hard for E is
incompressible by - DTIME(2 4n )
-reductions.
Since almost every language (and almost every language in E) is incompressible
by - DTIME(2 4n )
-reductions [7], Theorem 4.2 says that the - P
languages are "unusually simple" in at least this one respect.
The largest part of the proof of the Main Theorem is the construction of
a language H with the following two properties.
m -hard for E.
(II) H is incompressible by - DTIME(2 4n )
-reductions.
By Theorem 4.2, this language H cannot be - P
m -hard for E. A padding
argument then gives the Main Theorem.
The language H is constructed by diagonalization. In establishing property
(I), the construction uses a fixed rigid enumeration d
of all p-martingales. Such a rigid enumeration exists by Theorem 3.4. In
establishing property (II), the construction uses a fixed function f such that
is universal for DTIMEF(2 4n ), in the sense that
(The existence of such an efficient universal function
is well-known [3, 4].)
In addition to the pairing function h; i mentioned in section 2, the construction
of H uses the ordering !   of N 2 defined by
or [(1
and
for all j; m; k; n 2 N. It is easy to check that (N isomorphic to
(N; !). For (k; n) 2 N 2 , let
(j; m) 2 N 2
be the number of !   -predecessors of (k; n) in N 2 . Two important properties
of !   are that
and
Using the ordering !   , define the modified collision set C
i of a function
Also, for k 2 N, define the k th slice of C
i to be the set
Lemma 4.3. For all i 2 N, the function f i is one-to-one almost everywhere
if and only if the set C
i is finite.
Proof. Fix define an equivalence relation j i on f0; 1g   by
Then the collision set C f i
and the modified collision set C
i each consist of
all but one of the elements of all the non-singleton equivalence classes of j i .
It follows immediately that C f i
and C
are either both finite or both infinite.
Overview of the Construction. Informally and intuitively, the language
H is constructed by deciding the Boolean values hk; ni 2 H for successive
(k; n) in the ordering !   of N 2 . It is convenient to regard H as consisting
of the separate "strands" H

Figure

3.) The construction exploits the ordering !   to ensure that H
and each H k 2 E. The "ultimate objective" of each H k is to ensure that
a specially constructed martingale e
d k does not succeed on H k . For each k,
all but finitely many of the values are chosen according to this
ultimate objective. The exceptions occur when values are chosen
in order to "destroy" various functions f in order to
ensure that these functions are not many-one reductions of H.

Figure

3: The strands of H.
The specially constructed martingales are of the form e
where d k is taken from the rigid enumeration of all p-martingales given by
Theorem 3.4 and the martingales d i;k are defined below. Since e
d k does not
succeed on H k , d k also does not succeed on H k . Since k is arbitrary here and
each H k 2 Pm (H) " E, it follows that Pm does not have p-measure
0, i.e., that Pm (H) does not have measure 0 in E. Thus H is a weakly
m -hard for E. On the other hand, since e
d k does not succeed on H k , none
of the martingales d i;k succeeds on H k . Moreover, matters are arranged so
that, for every many-one reduction f i of H with C
succeeds on H k , or else f i is eventually "destroyed" by some value
It follows that H is incompressible by - DTIME(2 4n )
-reductions, whence H is
not - P
m -hard for E by Theorem 4.2.
Precise details follow.
The Construction. The language H ' f0; 1g   is defined by
where the languages H are defined, along with the auxiliary martingales
e
\Delta, by the following recursion.
(1) For k 2 N and w 2 f0; 1g   , define
e
d i;k (w);
where the functions d i;k are computed as follows. Assume that w 2
1g.
(a) d i;k
(b) If (k;
(c) If (k; n) 2 C
d i;k
where (j; m) is the !   -least pair in N 2 such that f i (hj;
It is clear that each d i;k , and hence each e
d k , is a martingale.
For k; r 2 N and w 2 f0; 1g   , the approximation
d k;r
d
d i;k (w)
of e
d k (w) is also used. It is easy to check that
for all k; r 2 N and w 2 f0; 1g   satisfying r
(2) In the construction of the languages H \Delta, the operation
"destroy f i at (k; n)"
is often performed. In all such instances, it is known that (k; n) 2 C
and the operation is performed by setting
where (j; m) is the !   -least pair in N 2 such that f i (hj;
Note that a single performance of this operation ensures that f i is not
a many-one reduction of H.
The sets
is destroyed at (j; m)g ;
for are also used in the construction. It is emphasized that
an index i appears in D k;n only if the operation "destroy f i at (j; m)"
is explicitly performed for some (j; m) !   (k; n). In particular, for each
(j; m), there is at most one i such that f i is destroyed at (j; m), even
though there are many i 0 such that f Thus each D k;n is a finite
set with jD k;n j - #   (k; n).
For
Note that '(k; n) is finite for all k; n 2 N (because f i is constant for
infinitely many i). The values are defined according to the
following two cases.
begin
do
begin
d k;n+1 (wb)
for
d k;n (w0) and
d k;n (w1).//
if '(k; n) - k
then destroy f '(k;n) at (k; n)
else
end.

Figure

4: Computation of in the proof of Lemma 4.4.
Case 1. If '(k; n) - k, then destroy f '(k;n) at (k; n).
Case 2. If '(k; n) ? k, then set
d k;n (w1) - b e
d k;n (w0)]];
This completes the construction of the languages H and the martingales
e
The following lemmas are used to prove the Main Theorem.
. For each k 2 N, H k 2 E.
Proof. Assume first that (k; n) 2 N 2 and that the values are
known (stored) for all pairs (j; m) !   (k; n), as is the set D k;n . Consider the
computation of exhibited in Figure 4.
To estimate the time required for this computation, recall the properties
of !   and note the following.
(i) The computation of w requires at most n \Delta #   (k;
steps.
(ii) The computation of b
d k;n+1 (wb) requires at most (3
steps.
(iii) For the condition "(k; n) 2 C
" can be tested in at most
steps.
(iv) By (iii), for the computation of d i;k (wb) requires at
most O(n steps.
(v) By (ii) and (iv), the entire computation of
d k;n (wb), i.e., the for-loop
in Figure 4, requires at most 2 O((1+jkj)(1+jnj)) +(2n+2)2 O((1+jkj)(1+jnj))
steps.
(vi) As in (iii), for the condition "(k; n) 2 C
" can be tested in
at most 2 O((1+jkj)(1+jnj)) steps. Thus, testing the condition "'(k; n) -
k," and computing '(k; n) if this condition is true, requires at most
steps. It follows easily that
the if-then-else in Figure 4 requires at most 2 O((1+jkj)(1+jnj)) steps.
By (i), (v), and (vi) above, the computation described in Figure 4 requires
at most 2 O((1+jkj)(1+jnj)) steps to compute given the set D k;n and
the values
The condition hk; ni 2 H can now be decided by computing and storing
the successive values according to the !   -ordering of N 2 , using
the computation in Figure 4 and updating D j;n at each stage. This requires
at most (1 steps. Since
proves that H 2 E 2 . Also, for fixed k,
Lemma 4.5. For all i 2 N, if there exist infinitely many k 2 N such that
the slice C
i;k is nonempty, then f i is not a many-one reduction of H.
Proof. Fix assume that the set
is infinite. For each k 2 S, let n
i;k . For every k 2 S, at least one
of the following four conditions must hold.
(In fact, for all real numbers a, b, and c, at least one of a ? c, a ! b,
must hold.) It is clear that condition (i) holds for only
finitely many k. For each k such that condition (iii) holds, the construction
of H ensures that f '(k;n k ) is destroyed at (k; n k ). Since each f j is destroyed
at most once in the construction of H, it follows that condition (iii) holds
for only finitely many k. Since S is infinite, this implies that there is some
such that condition (ii) or condition (iv) holds.
Fix such a number k. If condition (ii) holds, then i 2 D k;n k
(because
is not a many-one reduction of H. If condition (iv) holds,
then f i is destroyed at (k; n k ), so f i is not a many-one reduction of H. Thus,
in any case, f i is not a many-one reduction of H. 2
Lemma 4.6. For all is a many-one reduction of H and C
i;k is
infinite, then d i;k succeeds on H k .
Proof. Assume that is a many-one reduction of H, and C
i;k is
infinite. Consider the successive values
Clause (a) of the definition of d i;k says that r
clauses (b) and (c) ensure that each r n+1 2 f0; r g. In fact, since f i is
a reduction of H, clause (c) never causes r n+1 to be 0. We thus have the
recurrence
i;k .
Since C
i;k is infinite, this implies that r
succeeds on H k . 2
Lemma 4.7. For all k 2 N, e
d k does not succeed on H k .
Proof. Fix k 2 N and consider the manner in which the values are
decided for There can be at most finitely many values of n
for which Case 1 holds. (This is because each occurrence of Case 1 involves
a new value of '(k; n), with '(k; n) - k.) Thus there exists n 0 2 N such that
Case 2 holds for all n - n 0 . For all n 2 N, let
be the n-bit prefix of -H k
. Then, for all m - n 0 , Case 2 ensures that
e
d k;m (wm+1
d k;m (wm
d k;m (wm 1)+ 2 \Gammam
e
e
It follows that, for all n - n 0 ,
e
Thus, if
e
then
e
for all n 2 N. Hence e
d k does not succeed on H k . 2
Lemma 4.8. H is weakly - P
m -hard for E.
Proof. Let k 2 N. It is clear that H k 2 Pm (H) and S 1 [d k
d k ]. It
follows by Lemmas 4.4 and 4.7 that
whence Pm arbitrary here, this implies that
E) 6= 0, i.e., that -(Pm (H) j E) 6= 0. Thus H is weakly - P
for
Lemma 4.9. H is not - P
m -hard for E.
Proof. By Theorem 4.2, it suffices to show that H is incompressible by
-reductions. For this, fix i 2 N such that f i is a many-one reduction
of H. It suffices to show that f i is one-to-one almost everywhere.
Note the following two things.
(i) For each k 2 N, the slice C
i;k is finite by Lemmas 4.7 and 4.6.
(ii) By Lemma 4.5, there are only finitely many k 2 N such that C
Taken together, (i) and (ii) imply that C
i is finite. It follows by Lemma 4.3
that f i is one-to-one almost everywhere. 2
By Lemmas 4.4, 4.8, and 4.9, the language H
but not - P
m -hard, for E. From this, a simple padding argument suffices to
prove the Main Theorem.
Proof of Main Theorem. Let H be defined as above. By Lemma 4.4,
there is a polynomial q(n) - n such that H 2 DTIME(2 q(n) ). Let
It is easy to check that C 2 E and that Pm It follows by
Lemmas 4.8 and 4.9 that C is weakly - P
m -complete, but not - P
for
5 Conclusion
The most important problem suggested by this work is to find "natural"
examples of languages that are weakly - P
m -complete, but not - P
for E. As noted in section 1, such languages would provably be strongly
intractable. It is reasonable to hope that the study of such natural examples
would yield new insights into the nature of intractability.
It is especially intriguing to consider the possibility that SAT and other
natural NP-complete problems may be weakly - P
m -complete for E, i.e., that
NP may not have measure 0 in E. The hypothesis that SAT is weakly - P
complete for E implies, but may in some sense be stronger than, the P 6= NP
hypothesis. For example, recent work has shown that, if SAT is weakly
m -complete for E, then NP contains P-bi-immune languages [14], every
-hard language for NP is dense [11], every - P
-complete language for NP
has a dense exponential complexity core [7], and there is a language that is
T -complete, but not - P
m -complete, for NP [12]. Further investigation of the
consequences and reasonableness of this hypothesis is indicated.
It is routine to modify the proof of the Main Theorem to construct languages
that are weakly - P
m -complete, but not - P
m -complete, for larger classes
such as E 2 and ESPACE. A more interesting, and perhaps harder, question
concerns alternate versions of the Main Theorem in which - P
m is replaced by
other reducibilities. Homer, Kurtz, and Royer [5] have proven that a language
1\Gammatt -hard for E if and only if it is - P
m -hard for E. It follows immediately
that the language C given by the Main Theorem is weakly - P
but not - P
1\Gammatt -complete, for E. That is, the Main Theorem holds with - P
replaced by - P
1\Gammatt . Beyond this, little is known. New techniques may be
required to determine whether the Main Theorem holds with - P
replaced
by - P
T .

Acknowledgments

. I thank Jim Royer and Tom Linton for several useful
suggestions on an earlier draft of this paper.



--R

On isomorphism and density of NP and other complete sets
Measure Theory
On the computational complexity of algorithms


Some observations about the randomness of hard prob- lems
The complexity and distribution of hard problems
in preparation.
Category and measure in complexity classes
Almost everywhere high nonuniform complexity
the density of hard languages
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
The density and complexity of polynomial cores for intractable sets
Measure and Category
Real Analysis
Klassifikation der Zufallsgesetze nach Komplexit-at und Ordnung
A unified approach to the definition of random sequences
Lecture Notes in Mathematics 218
Process complexity and effective random tests
Complete sets and closeness to complexity classes
Provably difficult combinatorial games
Classifying the computational complexity of problems
--TR

--CTR
Stephen A. Fenner , Jack H. Lutz , Elvira Mayordomo , Patrick Reardon, Weakly useful sequences, Information and Computation, v.197 n.1/2, p.41-54, February 25, 2005/March 15, 2005
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
resource-bounded measure;weak completeness;complexity classes;computational complexity;complete problems