1 Introduction

The standard way for proving a problem to be intractable is to show that the problem is hard or complete for one of the standard complexity classes containing intractable problems. Lutz [18] proposed a generalization of this approach by introducing more general weak hardness notions which still imply intractability. While a set A is hard for a class C if all problems in C can be reduced to A (by a polynomial-time-bounded many-one reduction) and complete if it is hard and a member of C, Lutz proposed to call a set A weakly hard if a nonnegligible part of C can be reduced to A and to call A weakly complete if in addition A ∈C. For the exponential time classes E = DTIME(2lin) and EXP = DTIME(2poly), Lutz formalized these ideas by resource-bounded (Lebesgue) measures on these classes. He called a subclass of E negligible if it has an (effective) measure 0 in E. A variant of these concepts, based on resource-bounded Baire category in place of measure, was introduced by Ambos-Spies [4] where a class is declared to be negligible if it is meager in the corresponding resource-bounded sense.

A certain drawback of these weak hardness notions in the literature, called measure-hardness and category-hardness in the following, is that they are based on the somewhat technical concepts of resource-bounded measure and resource-bounded category, respectively. So here we introduce some alternative weak hardness notions which are conceptually much simpler and are solely based on the basic concepts of computational complexity theory.

While the weak hardness notions in the literature implicitly used the fact that, by the time-hierarchy theorem, the class E has a proper hierarchy of time complexity classes, where the individual levels are the deterministic-time classes Ek = DTIME(2kn) (k ≥ 1), our primary new weak hardness notion for E, called E-nontriviality, is based on this observation explicitly. We consider a subclass of E to be negligible, if it is contained in a fixed level Ek of the linear exponential time hierarchy. In other words, a set A is E-nontrivial if it has predecessors (under p-m-reducibility) from arbitrarily high levels of this hierarchy.

Since any level Ek of E has measure 0 in E and is meager in E, E-nontriviality generalizes the previously introduced weak hardness notions for E. On the other hand, since P ⊂E1, E-nontriviality still guarantees intractability. In fact, we may argue that E-nontriviality is the most general weak hardness notion for E if for such a notion we do not only require that it generalizes E-hardness and implies intractability but that it also reflects the internal, hierarchical structure of E hence considers finite parts of the linear exponential time hierarchy to be negligible.

The second new weak hardness notion we will consider, called strongE-nontriviality, is strictly between the weak notion of E-nontriviality and the stronger notions of measure- and category-hardness. A strongly E-nontrivial set does not only have predecessors from arbitrarily high levels E ∖Ek of the hierarchy E but, for any given k ≥ 1, it has a predecessor in E which is almost-everywhere complex for the k th level of the linear exponential time hierarchy, i.e., which is Ek-bi-immune. Note that measure- and category-hardness can be defined in a similar fashion as shown in [10] and [4], respectively: a set A is measure- (category-) hard for E if, for any k ≥ 1 there is a predecessor of A in E which is random (generic) relative to Ek. Intuititively, bi-immune, generic and random sets characterize certain types of diagonalizations. So the weak hardness concepts induced by these notions can be classified by the types of diagonalizetions which can be performed below the corresponding weakly hard sets.

The outline of the paper is as follows.

After formally introducing our new weak hardness notions for E - E-nontriviality and strong E-nontriviality - in Section 2, in Section 3 we give some examples of intractable but still E-trivial sets in E thereby showing that E-nontriviality is a strict refinement of intractability. First we observe that sets of sufficiently low hyper-polynomial complexity are E-trivial. Though this observation is not surprising, it gives us some first nontrivial facts on the distribution of the E-trivial and the E-nontrivial sets in E. For instance it implies that the only sets which code all E-trivial sets in E (i.e., more formally, the only sets to which all E-trivial sets in E are p-m-reducible) are the E-hard sets. We then show (what might be more surprising) that there are E-trivial sets in E of arbitrarily high complexity, i.e., that, for any k ≥ 1, there is an E-trivial set in E ∖Ek. In fact, by generalizing a result of Buhrman and Mayordomo [13] for measure hardness, we obtain some natural examples of such sets by showing that the sets of the Kolmogorov-random strings w.r.t. exponential-time-bounded computations are E-trivial.

In Section 4 we give some examples of (strongly) E-nontrivial sets and give a separation theorem for the weak E-completeness notions mentioned before. In order to show that there are strongly E-nontrivial sets in E which are not category and measure complete for E and that there are E-nontrivial sets which are not strongly E-nontrivial we analyse the minimum density of the complete sets under the various weak hardness notions considered here. In particular, we show that there are tally strongly E-nontrivial sets in E whereas no category complete (hence no measure complete) set for E has this property, and that there are exptally E-nontrivial sets in E whereas no strongly E-nontrivial set in E has this property.

In Section 5 we analyse the information content of weakly complete sets (i.e., more formally the p-m-degrees of the weakly complete sets) thereby giving some more structural differences among the complete sets under the various weak hardness notions. For instance we show, that the effective disjoint union of two E-trivial sets is E-trivial again, and that E-trivial sets don’t help. The latter means that if an E-hard set H can be reduced to the effective disjoint union of sets A and B where A is E-trivial then H can be reduced to B already, i.e., B is E-hard. In other words, if we decompose an E-complete set into two incomplete parts then both parts are E-nontrivial. For the other weak hardness notions the corresponding facts fail. In fact, any set A ∈E can be split into two sets which are not strongly E-non-trivial.

Finally, in Section 6 we give a short summary of results on some other aspects of our new weak hardness notions which will be presented in more detail elsewhere.

We conclude this section by introducing some notation and by summarizing some basic definitions and facts related to the exponential time classes to be used in the following.

Our notation is standard. Unexplained notations can be found in the monographs of Balcázar et al. [11] and [12]. We let Σ∗ = {0,1}∗ be the set of all (finite binary) strings. A set or problem or language is a subset of Σ∗, a class is a set of sets, i.e., a subset of the power set of Σ∗. Strings will be denoted by lower case letters from the end of the alphabet (u, …, z, un, …), sets by italic capital letters (A, B, C, …, An, …), and classes by straight capital letters (A, B, C, …, An, …). The (n + 1)th string with respect to the length-lexicographical ordering ≤ is denoted by zn, i.e., z0 = λ,z1 = 0,z2 = 1,z2 = 00,…. Note that |zn|≈ log(n) where |x| denotes the length of x. For a set A and string x we write A(x) = 1 if x ∈ A and A(x) = 0 if x∉A.

The exponential time classes we will deal with are the classes

$$ \mathrm{E} = \bigcup_{k \geq 1} \text{DTIME}(2^{kn}) \text{} (Linear Exponential Time) $$
(1)
$$ \text{EXP} = \bigcup_{k \geq 1} \text{DTIME}(2^{n^{k}}) \text{} (Polynomial Exponential Time) $$
(2)

where we will use the following abbreviations for the individual levels of these classes:

$$ \mathrm{E}_{k} = \text{DTIME}(2^{kn}) \text{ and } \text{EXP}_{k} = \text{DTIME}(2^{n^{k}}). $$

Note that, by the time-hierarchy theorem, the hierarchies of the linear exponential time classes and of the polynomial exponential time classes are proper, and that

$$ \mathrm{E_{1}} = \text{EXP}_{1} \subset \mathrm{E} \subset \text{EXP}_{2}. $$

For comparing the complexity of problems we use the polynomial-time-bounded version of many-one reducibility (p-m-reducibility for short) where a set B is p-m-reducible to a set A (\(B {\leq ^{p}_{m}} A\)) via f if f is a polynomial-time computable function f : Σ∗→Σ∗ and B(x) = A(f(x)) holds for all strings x. Note that \({\leq ^{p}_{m}}\) is a preordering, i.e., reflexive and transitive. So p-m-equivalence is an equivalence relation where sets A and B are p-m-equivalent (\(A {\equiv ^{p}_{m}} B\)) if \(A {\leq ^{p}_{m}} B\) and \(B {\leq ^{p}_{m}} A\) hold.

We call B a predecessor of A (and A a successor of B) if B is p-m-reducible to A, and we let \(\mathrm {P}_{m}(A) = \{B: B {\leq ^{p}_{m}} A\}\) denote the class of predecessors of A under p-m-reducibility. A set A is hard for a class C (or C-hard for short) if C ⊆Pm(A), i.e., if any set in C is p-m-reducible to A, and A is complete for a class C (or C-complete for short) if A is a member of C and A is C-hard.

The (downward) closure of a class C under p-m-reducibility is the class of the predecessors of the members of C,

$$ \mathrm{P}_{m}(\mathrm{C}) = \bigcup_{A \in \mathrm{C}} \mathrm{P}_{m}(A), $$

and a class \(\mathcal {C}\) is closed under p-m-reducibility if Pm(C) = C holds.

Note that EXP is closed under p-m-reducibility, i.e., Pm(EXP) = EXP. The other exponential classes E,Ek,EXPk, however, are not closed under p-m-reducibility. This is a consequence of the well known Padding Lemma.

Lemma 1 (Padding Lemma)

For any setA ∈Ek,the setAk = {0k⋅|x|1x : x ∈ A} is in E1and p- m-equivalent to A, and, for any setA ∈EXPk,the set\(\hat {A}_{k} = \{0^{|x|^{k}}1x: x \in A\}\)isin E1and p- m-equivalent to A.

So, by closure of EXP under p-m-reducibility and by the trivial relations among the exponential time classes,

$$\mathrm{P}_{m}(\mathrm{E}_{k}) = \mathrm{P}_{m}(\mathrm{E}) = \mathrm{P}_{m}(\text{EXP}_{k}) = \mathrm{P}_{m}(\text{EXP}) = \text{EXP}$$

(for all k ≥ 1). Though E is not closed under p-m-reducibility, we will use the observation that E is closed under p-m-reductions of linearly bounded size.

Lemma 2

Assume thatA ∈Ekand\(B {\leq ^{p}_{m}} A\)via f where |f(x)|≤ k′⋅|x| + k″for all x (k,k′≥ 1,k″≥ 0).Then\(B \in \mathrm {E}_{k \cdot k^{\prime }}\).

Proof

Given a string x of length n, B(x) can be computed using the identity B(x) = A(f(x)) where, by |f(x)|≤ k′⋅ n + k″ and by A ∈DTIME(2kn), A(f(x)) can be computed in \(O(2^{k \cdot (k^{\prime } \cdot n + k^{\prime \prime })}) \leq O(2^{k \cdot k^{\prime }})\) steps. □

2 E-Nontriviality and Strong E-Nontriviality

We now introduce the two new central notions which we will study in this paper. As pointed out in the introduction these notions have been inspired by Lutz’s idea of generalizing hardness and completeness for a complexity class C ⊃P in such a way that hardness still guarantees intractability. Following Lutz [18], we call a problem A weakly hard for a complexity class C if a nonnegligible part of the problems in C can be p-m-reduced to A, and we call Aweakly complete if A ∈C and A is weakly hard for C. In order to guarantee that such a weak hardness notion meets its goals, the family of the nonnegligible subclasses of C must have the following properties:

  1. (i)

    The class C itself has to be nonnegligible thereby guaranteeing that any hard (complete) set for C (under p-m-reducibility) is weakly hard (weakly complete).

  2. (ii)

    The class P of the polynomial time computable sets has to be negligible thereby guaranteeing that weakly hard problems for C are intractable.

Moreover, it is natural to require that subclasses of negligible classes are negligible again and that finite unions of negligible classes remain negligible:

  1. (iii)

    For any subclasses C′,C″ of C such that C′⊆C″ and C″ is negligible, C′ is negligible too.

  2. (iv)

    For negligible subclasses C′,C″ of C, C′∪C″ is negligible too.

Finally, the definition of negligibility should reflect the structure of C.

For the linear exponential time class E = DTIME(2lin) (and for other sufficiently closed complexity classes like the polynomial exponential time class EXP), Lutz formalized these ideas by introducing a resource-bounded (pseudo) measure on this class and by saying that a subclass of E is negligible if it has measure 0 in E. He then showed that there are weakly complete sets for E which are not complete and that the above conditions (i) - (iv) are satisfied whence the corresponding weak hardness and completeness notions are meaningful. He also showed that his negligibility notion reflects the hierarchical structure of E as follows.

  1. (v)

    For any k ≥ 1, Ek is negligible.

I.e. a class which intersects only finitely many of the infinitely many levels of \(\mathrm {E} = \bigcup _{k \geq 1} \mathrm {E}_{k}\) is negligible.

In the following we refer to the weak hardness (completeness) notion of Lutz [18] which is based on the measure on E as measure hardness (measure completeness) forE or E-measure hardness (E-measure completeness) for short.

Following Lutz [18], Ambos-Spies [4] introduced alternative weak hardness notions for E which are based on Baire category in place of measure. Correspondingly, the negligible subclasses of E are now those which are meager in E. In fact, there are several Baire category concepts for E discussed in [4], but one of the concepts - called AFH-category there - proved to be of particular interest since it is compatible with measure, namely AFH-meager subclasses of E have measure 0 in E while the converse in general fails. So the corresponding weak hardness concept is strictly more general than Lutz’s measure hardness.

In the following we refer to the weak hardness (completeness) notion of Ambos-Spies [4] based on AFH-category on E as category hardness (category completeness) for E or E-category hardness (E-category completeness) for short.

Though the weak hardness and completeness notions of Lutz [18] and Ambos-Spies [4] are very intuitive in being based on two of the classical systems for measuring the size of a class, namely Lebesgue measure and Baire category, a certain drawback of these notions is that the underlying resource-bounded measure and category notions are somewhat technical. (For this reason we also do not introduce these concepts here formally.) So here we propose alternative weak hardness notions for E which are solely based on standard concepts of complexity theory.

By our above analysis, the most general negligibility notion for E which reflects the structure of E (i.e., satisfies (v) above) is obtained by calling a subclass of E negligible if it is contained in one of the levels Ek of E. (As one can easily check, this notion of negligibility satisfies the other above conditions (i) to (iv) too.) In other word, a subclass C of E is nonnegligible if it has members from arbitrary high levels of the linear exponential hierarchy E. We call the corresponding weak hardness notion E-nontriviality.

Definition 1

A set A is trivial for E (or E-trivial for short) if

$$ \exists k \geq 1 (\mathrm{P}_{m}(A) \cap \mathrm{E} \subseteq \mathrm{E}_{k}) $$
(3)

holds, and A is nontrivial for E (or E-nontrivial for short) otherwise, i.e., if

$$ \forall k \geq 1 \exists B \in \mathrm{E} (B {\leq^{p}_{m}} A \& B \not\in \mathrm{E}_{k}) $$
(4)

holds.

The second concept we will consider here is a strengthening of E-nontriviality and is called strong E-nontriviality. While, for an E-nontrivial set A, we require that, for any k ≥ 1, there is a set B in E which can be p-m-reduced to A and which is infinitely often 2kn-complex (i.e., any algorithm computing B requires more than 2k|x| steps for infinitely many inputs x), for a strongly E-nontrivial set A we require that there is such a set B which is almost-everywhere 2kn-complex (i.e., any algorithm computing B requires more than 2k|x| steps for all but finitely many inputs x). Since almost everywhere complexity coincides with bi-immunity, i.e., since a set A is a.e. t(n)-complex if and only if A is DTIME(t(n))-bi-immune (see Balcázar et al. [12]), we formally define strong E-nontriviality in terms of bi-immunity. Recall that a set A is C-bi-immune for a class C if there is no infinite set B ∈C such that B ⊆ A or B ∩ A = ∅.

Definition 2

A set A is strongly nontrivial for E (or strongly E-nontrivial for short) if

$$ \forall k \geq 1 \exists B \in \mathrm{E} (B {\leq^{p}_{m}} A \& B \text{ is }\mathrm{E}_{k}\text{-bi-immune}) $$
(5)

holds; and A is weakly trivial for E (or weakly E-trivial for short) otherwise.

Note that, for any Ek-bi-immune set B, B∉Ek. So, any strongly E-nontrivial set A is E-nontrivial. Also note that strong E-nontriviality may be viewed as weak hardness for E if we call a subclass C of E nonnegligible if it contains Ek-bi-immune sets for all k ≥ 1. Obviously, this negligibility notion satisfies the conditions (ii) - (v) above. That it satisfies conditon (i) too follows for instance from the time-hierarchy theorem for a.e. complexity by Geske et al. [14] which implies that there are Ek-bi-immune sets in Ek+ 1 (for any k ≥ 1). In fact, as shown by Ambos-Spies [4], any E-category hard set has predecessors in E which are Ek-bi-immune (for all k ≥ 1). So E-category hard sets hence E-measure hard sets are strongly E-nontrivial. So we obtain the following relations among the weak hardness notions for E.

Lemma 3

For any set A the following hold.

$$ \begin{array}{@{}rcl@{}} &&A \mathrm{E}\text{-hard}\\ && \Downarrow\\ &&A \mathrm{E}\text{-measure hard}\\ && \Downarrow\\ &&A \mathrm{E}\text{-category hard}\\ && \Downarrow\\ &&A \text{strongly } \mathrm{E}\text{-nontrivial}\\ && \Downarrow\\ &&A \mathrm{E}\text{-nontrivial}\\ && \Downarrow\\ &&A \text{intractable} \end{array} $$
(6)

Proof

The first implication (from top) has been shown in Lutz [18], while, as pointed out before, the second and third implications have been shown in Ambos-Spies [4]. The fourth implication follows from the fact that no set in Ek is Ek-bi-immune. Finally, the last implication follows from the fact that P ⊂ E1. □

Lutz [18] and Ambos-Spies [4] have shown that the first two implications in Lemma 3 are strict, even if we consider only sets in E (i.e., the corresponding weak completeness notions). In the following sections we will show that the other implications are strict too. Namely, in Section 3 we give examples of intractable sets in E which are E-trivial, and in Section 4 we show that there are E-nontrivial sets which are weakly E-trivial and that there are strongly E-nontrivial sets which are not E-category hard. The last two of these results are obtained by analysing the densities of the different types of weakly hard sets.

We conclude this section with some simple observations on the E-nontrivial and strongly E-nontrivial sets.

Note that the class of the (strongly) E-nontrivial sets is closed upwards under \({\leq ^{p}_{m}}\) hence, in particular, closed under p-m-equivalence. By definition, an E-nontrivial set A has predecessors in infinitely many levels Ek+ 1 ∖Ek of the linear exponential hierarchy E. In fact, an E-nontrivial set has predecessors in all of these levels:

Lemma 4

Let A be E-nontrivial.Then

$$ \forall k \geq 1 \exists B \in \mathrm{E}_{k + 1} \setminus \mathrm{E}_{k} (B {\leq^{p}_{m}} A) $$
(7)

holds.

Lemma 4 directly follows from the following variation of the Padding Lemma which is obtained by calibrating the amount of padding.

Lemma 5 (Second Padding Lemma)

Let A andk ≥ 1 be given such thatA ∈Ek+ 1 ∖Ek.Then, for anyk′≤ k(withk′≥ 1),there is a set\(A^{\prime } \in \mathrm {E}_{k^{\prime }+ 1} \setminus \mathrm {E}_{k^{\prime }}\)suchthat\(A^{\prime } {\equiv ^{p}_{m}} A\).

Proof

(Sketch) Given k ≥ 2 and A ∈Ek+ 1 ∖Ek, let A′ = {0f(|x|)1x : x ∈ A} for \(f(n) = \lfloor \frac {n}{k} \rfloor \). Then, as one can easily show, \(A^{\prime } {\equiv ^{p}_{m}} A\) and A′∈Ek ∖Ek− 1. The claim follows by induction. □

For strongly E-nontrivial sets we can make the observation corresponding to Lemma 4 too. By definition, for a strongly E-nontrivial set A there are infinitely many k such that A has a predecessor B ∈E which is Ek-bi-immune but not Ek+ 1-bi-immune. By applying the Second Padding Lemma above one may argue that this is in fact true for all k:

$$ \forall k \geq 1 \exists B \in \mathrm{E} \cap \mathrm{P}_{m}(A) (B \text{ is }\mathrm{E}_{k}\text{-bi-immune} \& B \text{ is not }\mathrm{E}_{k + 1}\text{-bi-immune}) $$
(8)

We omit the proof and rather give another alternative characterization of strong E-nontriviality that is of greater technical interest.

Theorem 1 (Characterization Theorem for Strong Nontriviality)

A set A is strongly E-nontrivialif and only if there is an E1-bi-immunesetB ∈E such that\(B {\leq ^{p}_{m}} A\).

The nontrivial direction of Theorem 1 follows from the following lemma by considering the sets Bk there for a given E1-bi-immune predecessor B of A in E.

Lemma 6

Let B be E1-bi-immune.Then, for anyk ≥ 1,there is an Ek-bi-immunesetBkand an EXPk-bi-immuneset\(B^{\prime }_{k}\)suchthat\(B_{k}, B^{\prime }_{k} \in \mathrm {P}_{m}(B)\).If moreoverB ∈E then the setBkcan be chosen such thatBk ∈E too.

Proof

The idea is taken from Ambos-Spies et al. [10] where a similar lemma for randomness in place of bi-immunity is proven. So we only sketch the proof.

Let Bk = {x : 0k|x|1x ∈ B} and \(B^{\prime }_{k} = \left \{x: 0^{|x|^{k}}1x \in B\right \}\). Then \(B_{k} {\leq ^{p}_{m}} B\) via f(x) = 0k|x|1x and \(B^{\prime }_{k} {\leq ^{p}_{m}} B\) via \(g(x)= 0^{|x|^{k}}1x\). Moreover, if B ∈E then, by Lemma 2, Bk ∈E too since f is linearly bounded.

It remains to show that Bk is Ek-bi-immune and \(B^{\prime }_{k}\) is EXPk-bi-immune. We will prove the former, the proof of the latter is similar.

For a contradiction assume that Bk is not Ek-bi-immune. Then, by symmetry, we may assume that there is an infinite set C′⊆ Bk such that C′∈Ek. Let C = {0k|x|1x : x ∈ C′}. Then, by infinity of C′, C is infinite, and, by C′⊆ Bk and by definition of Bk, C ⊆ B. Moreover C ∈E1, since, for a string y we can decide whether y ∈ C by first checking (in polynomial time) whether there is a string x such that y = 0k|x|1x and, if so, by checking in O(2k|x|) ≤ O(2|y|) steps whether x ∈ C′. So B is not E1-bi-immune contrary to assumption. □

3 Some Examples of E-Trivial Sets in E

In order to show that, for sets in E, E-nontriviality does not coincide with intractability, here we give some examples of intractable but E-trivial sets in E. As one might expect, sets of sufficiently low time complexity are E-trivial. As we will also show, however, E-trivial sets can be found at all levels of the linear-exponential hierarchy. Moreover, the sets of random strings under time bounded Kolmogorov complexity provide examples of intractable E-trivial sets.

We obtain our first examples of intractable E-trivial sets by the following observation on sets of low complexity.

Lemma 7

Let t be a nondecreasing, time constructible function such that, for somenumberk ≥ 1,

$$ t(p(n)) \leq_{a.e.} 2^{kn} $$
(9)

for all polynomials p. Then any set A ∈DTIME(t(n)) is E-trivial.

Proof

Given A ∈DTIME(t(n)) it suffices to show that Pm(A) ⊆Ek. So fix B ∈Pm(A), let f be a polynomial time computable function f such that \(B {\leq ^{p}_{m}} A\) via f , and let p be a polynomial time bound for f . Then B(x) can be computed by using the identity B(x) = A(f(x)) in O(p(|x|) + t(p(|x|))) steps since it takes at most p(|x|) steps to compute f(x) and, by A ∈DTIME(t(n)) and by |f(x)|≤ p(|x|), it takes at most t(p(|x|)) steps to compute A(f(x)) for the given string f(x). So, by (9), B(x) can be computed in O(2kn) steps, i.e., B ∈Ek. □

Theorem 2

There is an E-trivialsetA ∈E ∖P.

Proof

By Lemma 7 it suffices to show that there is a nondecreasing time constructible function t such that P ⊂DTIME(t(n)) and such that t(p(n)) ≤a.e.2n for all polynomials p.

Note that, for any polynomial p,

$$p(n) \leq_{a.e.} 2^{(\log n)^{2}} \leq_{a.e.} 2^{(\log n)^{4}} \text{ and } 2^{(\log n)^{4}} \not\in O(2^{(\log n)^{2}} \cdot \log(2^{(\log n)^{2}})).$$

So \(\mathrm {P} \subseteq \text {DTIME}\left (2^{(\log n)^{2}}\right ) \subset \text {DTIME}\left (2^{(\log n)^{4}}\right )\) where strictness of the latter inclusion holds by the time-hierarchy theorem. Moreover, \(2^{(\log p(n))^{4}} \leq _{a.e.} 2^{n}\) for all polynomials p. So the nondecreasing and time constructible function \(t(n) = 2^{(\log n)^{4}}\) has the required properties. □

Theorem 2 can be strengthened by using some results on the p-m-degrees of hyperpolynomial shifts proven in Ambos-Spies [3]. Here a set Ah = {1h(|x|)0x : x ∈ A} is called a hyperpolynomial shift of A if h is a time constructible, nondecreasing function \(h: \mathbb {N} \to \mathbb {N}\) such that h dominates all polynomials. Note that, for any hyperpolynomial shift Ah of a set A ∈EXP, Ah ∈DTIME(t(n)) for a function t(n) as in Lemma 7 whence Ah is E-trivial. Moreover, in [3] it has been shown that,

  1. (i)

    for any set A∉P and for any hyperpolynomial shift Ah of A, Ah is a strict predecessor of A, i.e., \(A_{h} <^{p}_{m} A\) and

  2. (ii)

    for any computable sets A and B such that \(A {\not \leq ^{p}_{m}} B\) there is a hyperpolynomial shift Ah of A such that \(A_{h} {\not \leq ^{p}_{m}} B\).

These results imply the following facts on the distribution of the E-trivial sets in E w.r.t. p-m-reducibility.

Theorem 3

  1. (a)

    For any setA ∈E ∖P there is an E-trivialsetT ∈E ∖P such that\(T <^{p}_{m} A\).

  2. (b)

    For any computable set B which is notE-hardthere is an E-trivialsetT ∈E such that\(T {\not \leq ^{p}_{m}} B\).

Proof

As observed above, for any set A ∈E and any hyperpolynomial shift Ah of A, Ah ∈E, Ah is E-trivial, and (by (i)) \(A_{h} <^{p}_{m} A\). So for a proof of (a) it suffices to show that for given A ∈E ∖P there is a hyperpolynomial shift Ah of A such that Ah∉P. But this follows from (ii) above by letting B be any polynomial time computable set. Similarly, for a proof of (b) it suffices to show that there is a set A ∈E which possesses a hyperpolynomial shift Ah such that \(A_{h} {\not \leq ^{p}_{m}} B\). But this follows from (ii) too by letting A be any E-complete set. □

Note that, by part (a) of Theorem 3 any intractable set in E bounds an intractable E-trivial set in E while, by part (b), the only sets in E which bound all the E-trivial sets in E are the E-complete sets.

Having given examples of intractable E-trivial sets of low hyperpolynomial complexity, we now show that there are E-trivial sets at arbitrarily high levels E ∖Ek of the E-hierarchy. (So, by Lemma 5, there are E-trivial sets at all levels Ek+ 1 ∖Ek of the E-hierarchy.)

Theorem 4

For anyk ≥ 1 there is an E-trivialset A in E ∖Ek.

The idea of the proof is as follows. Given k ≥ 1, by a diagonalization argument we construct a set A ∈Ek+ 2 ∖Ek such that any set B which is p-m-reducible to A will be p-m-reducible to A via a polynomial-time computable function f such that |f(x)|≤ 2|x|. Then, by Lemma 2, Pm(A) ⊆E2(k+ 2). So A is E-trivial.

To be more precise, we will apply the following lemma generalizing Lemma 2.

Lemma 8 (Boundedness Lemma)

Let A and B be sets and let f be apolynomial time computable function such thatA ∈Ek,\(B {\leq ^{p}_{m}} A\)via f, and

$$ \forall x (|f(x)| \leq k^{\prime} \cdot |x| + k^{\prime\prime} \text{ or } f(x) \not\in A) $$
(10)

(for some k,k′≥ 1,k″≥ 0). Then \(B \in \mathrm {E}_{k^{\prime } \cdot k}\).

Proof

Using the identity B(x) = A(f(x)) we can compute B(x) for a given string x of length n in \(O(2^{(k^{\prime } \cdot k)n})\) steps as follows. First, in poly(n) steps, compute f(x). Then, again in poly(n) steps, check whether |f(x)|≤ k′⋅ n + k″ or not. If not, then B(x) = A(f(x)) = 0. If so, by A ∈Ek, compute B(x) = A(f(x)) in \(O(2^{k \cdot |f(x)|}) \leq O(2^{k \cdot (k^{\prime } \cdot n + k^{\prime \prime })}) = O(2^{(k^{\prime } \cdot k)n})\) steps. □

Proof

of Theorem 4 Fix k ≥ 1 and let \(\{{E^{k}_{e}}: e \geq 0\}\) and {fe : e ≥ 0} be enumerations of Ek and of the class of the polynomial time computable functions, respectively, such that \({E^{k}_{e}}(x)\) can be computed in time O(2(k+ 1)max(e,|x|)) and fe(x) can be computed in time O(2max(e,|x|)) (uniformly in e and x).

By a diagonal argument we define a set A ∈Ek+ 2 which meets the requirements

$$ \Re_{2e}: A \not= {E^{k}_{e}} $$

and

$$ \Re_{2e + 1}: \forall x \in {\Sigma}^{*} (|f_{e}(x)| > |x|+e + 1 \Rightarrow f_{e}(x) \not\in A) $$

for e ≥ 0.

Obviously, the requirements with even indices ensure that A∉Ek. Similarly, by A ∈Ek+ 2, the requirements with odd indices ensure that A is E-trivial since, by Lemma 8, Pm(A) ⊆Ek+ 2.

For the definition of A, call a string yforbidden if y = fe(x) for some number e and some string x such that |x| + e + 1 < |y|, and let F be the set of forbidden strings. Then, in order to meet the requirements R2e+ 1 (e ≥ 0) it suffices to ensure that no forbidden string is put into A, i.e., to enusre that A ∩ F = ∅.

Note that the number f(n) of pairs (x,e) such that |x| + e + 1 < n is less than 2n. Namely, for n ≤ 1, f(n) = 0 and, for n ≥ 2,

$$ \begin{array}{lll} f(n) & = & |\{(x,e): |x|+e + 1 < n\} |\\ &&\\ & = & {\sum}_{e = 0}^{n-2} |\{x: |x| < n-(e + 1)\}|\\ &&\\ & = & {\sum}_{e = 0}^{n-2} (2^{n-(e + 1)}-1)\\ &&\\ & = & {\sum}_{e = 1}^{n-1} (2^{e} -1)\\ &&\\ & < & {\sum}_{e = 0}^{n-1} 2^{e}\\ &&\\ & = & 2^{n}-1. \end{array} $$

So the question of whether a string y of length n is forbidden can be decided in O(22n) steps since it suffices to compute for each of the f(n) < 2n pairs (x,e) statisfying |x| + e + 1 < n the value of fe(x) which, by choice of the functions fe, can be done in O(2n) steps. So F ∈E2. Moreover, since f(n) is a bound on the number of forbidden strings of length n, at least one of the 2n strings of length n is not forbidden, i.e, \(\overline {F} \cap \{0,1\}^{n} \not = \emptyset \) for all n ≥ 0.

So if we let \(A =\{y_{e}: y_{e} \not \in {E^{k}_{e}}\}\) where ye is the least string of length e which is not forbidden then the even-index requirements R2e are met by \(A(y_{e}) \not = {E^{k}_{e}}(y_{e})\) and the odd-index requirements are met since A ∩ F = ∅. Finally, A ∈Ek+ 2. Namely, by F ∈E2, the string ye of length e can be found in O(23e) ≤ O(2(k+ 2)e) steps, and, by choice of the enumeration of the sets \({E^{k}_{e}}\), \({E^{k}_{e}}(y_{e})\) can be computed in O(2(k+ 1)e) steps. □

Alternatively we can obtain E-trivial sets of high complexity in E by refining a result of Buhrman and Mayordomo [13] on sets of random strings in the setting of time-bounded Kolmogorov complexity.

For a Turing machine M and a time bound t, the t-bounded M-Kolmogorov complexity of a string x is defined as the length of the shortest input y on which M outputs x within t(|x|) steps:

$$ {C_{M}^{t}}(x) = \min\{|y|: M(y) = x \text{ in time }t(|x|)\} $$

By the Time-Bounded Invariance Theorem (see Li and Vitanyi [17], Theorem 7.1), there is a universal Turing machine U such that for any Turing machine M there is a constant cM such that, for any computable time bound t,

$$ \forall x (C^{c_{M} \cdot t \cdot log(t)}_{U}(x) \leq {C^{t}_{M}}(x)+c_{M}). $$
(11)

Then \(C^{t}(x) = {C^{t}_{U}}(x)\) is called the t-bounded Kolmogorov complexity of x, and the string x is called t-K-random if x cannot be compressed by U in time t(|x|), i.e., if Ct(x) ≥|x|. Finally, the set of all t-K-random strings is denoted by Rt:

$$R^{t} = \{x : C^{t}(x) \geq |x|\}$$

As Buhrman and Mayordomo [13] have shown, for tk(n) = 2kn (k ≥ 2), \(R^{t_{k}} \not \in \mathrm {P}\), \(R^{t_{k}} \in \mathrm {E}_{k + 2}\), and \(R^{t_{k}}\) is not weakly measure hard for E. In the following we strengthen the latter by showing that \(R^{t_{k}}\) is E-trivial.

Theorem 5

Fortk(n) = 2kn(k ≥ 2),the set\(R^{t_{k}}\)ofthetk- K-randomstrings is E-trivial.

Proof

Since \(R^{t_{k}} \in \mathrm {E}\), by Lemma 8 it suffices to show that, for any set A and any polynomial time computable function f such that \(A {\leq ^{p}_{m}} R^{t_{k}}\) via f ,

$$ \forall^{\infty} x (|f(x)| > 2|x| \Rightarrow f(x) \not\in R^{t_{k}}) $$
(12)

holds. Intuitively, this must be true, since for x such that |f(x)| > 2|x| the string f(x) is compressible since f(x) can be computed in polynomial time from the shorter string x.

More formally, let M be a Turing machine which computes f(x) and let p be a polynomial bound for M. Then \({C^{p}_{M}}(f(x)) \leq |x|\) for all x. So, by (11),

$$C^{c_{M} \cdot p \cdot log(p)}(f(x)) \leq |x|+c_{M}.$$

It follows that, for n0 such that cM ⋅ p(n) ⋅ log(p(n)) < 2n and n + cM < 2n for n ≥ n0,

$$C^{t_{k}}(f(x)) < 2|x|$$

for all strings x of length ≥ n0. So (12) holds for all strings x of length ≥ n0. Namely for such a string x such that |f(x)| > 2|x|, \(C^{t_{k}}(f(x)) < 2|x| < |f(x)|\) whence \(f(x) \not \in R^{t_{k}}\). □

Remark 6

  1. 1.

    While for an E-trivial set A we only require that Pm(A) ∩E ⊆Ek for some k ≥ 1, all of the E-trivial sets A obtained in this section have a stronger property, namely, satisfy Pm(A) ⊆Ek for some k ≥ 1. We may call sets with this stronger property strictly E-trivial. Note that any strictly E-trivial set is in E (since A ∈Pm(A)). So E-trivial sets outside of E cannot have this stronger property. An example of an E-trivial set A in E which is not strictly E-trivial is given in [8]. In fact the set A ∈E given there has predecessors from all levels EXPk+ 1 ∖EXPk of the polynomial exponential time hierarchy EXP but it has predecessors only from finitely many levels Ek+ 1 ∖Ek of the linear exponential time hierarchy E.

  2. 2.

    In this paper we only look at E-(non)trivial sets in E, i.e., investigate (strong) E-nontriviality as a weak completeness notion, and do not consider the corresponding, more general weak hardness notion. So we only remark here that outside of E we can find computable E-trivial sets of arbitrarily high time complexity. Moreover, there are noncomputable E-trivial sets. In fact, the class of E-trivial sets has (classical) Lebesgue measure 1.

    These observations immediately follow from results about p-m-minimal pairs in the literature. (Sets A∉P and B∉P form a p-m-minimal pair if, for any set C such that \(C {\leq ^{p}_{m}} A\) and \(C {\leq ^{p}_{m}} B\), it holds that C ∈P.) It suffices to observe that, for sets A and B such that B is DTIME(t(n))-hard for any computable function t(n) dominating the functions 2kn for k ≥ 1 and such that A and B form a minimal pair, A∉DTIME(t(n)) and A is E-trivial. So the existence of computable E-trivial sets of arbitrarily high time complexity follows from Ambos-Spies [2] where it has been shown that, for any computable set B∉P there is computable set A such that A and B form a minimal pair. Similarly, the fact that the class of E-trivial sets has measure 1 follows from the observation in [1] that, for any set C∉P, the upper cone \(\{D: C {\leq ^{p}_{m}} D\}\) of C has measure 0, which - by countable additivity of the measure - implies that for B∉P the class of sets A forming a minimal pair with B has measure 1 (since A and B are a minimal pair if and only if A is not in the upper cone of any of the countable many sets C∉P which are p-m-reducible to B).

4 On the Density of E-Nontrivial and Strongly E-Nontrivial Sets

In this section we will separate the different weak completeness notions for E by looking at the possible densities of the weakly complete sets. For the previously introduced weak completeness notions, E-measure completeness and E-category completeness, such density results can be found in the literature or can be easily derived from results there.

Theorem 7 (Lutz and Mayordomo 19)

Let A be E-measurecomplete. Then A is exponentially dense.

Theorem 8

  1. (a)

    There is an E-categorycomplete set A which is sparse.

  2. (b)

    No E-categorycomplete set is tally.

Here a set A is exponentially dense if there is a real 𝜖 > 0 such that, for almost all n,

$$|A^{\leq n}| = |A \cap \{x: |x| \leq n\}| > 2^{n^{\epsilon}};$$

A is sparse if there is a polynomial p such that |A≤n|≤ p(n); and A is tally if A ⊆{0}∗. (Note that tally sets are sparse while exponentially dense sets are not sparse.)

The proof of Theorem 8 uses some relations between E-category completeness and resource-bounded genericity together with some properties of these notions which can be found in the literature. Since the notions themselves are not required for the proof, we omit the quite technical definitions and refer the interested reader to Ambos-Spies [4] for a detailed discussion of these concepts.

Proof

(of Theorem 8) For a proof of (a) it suffices to note that any n2-generic set in E is E-category complete (see Ambos-Spies [4]) and that there are sparse n2-generic sets in E (see Ambos-Spies, Neis, Terwijn [10]).

For a proof of (b) let A be E-category complete and, for a contradiction, assume that A is tally. By the former, there is an n2-generic set B ∈E such that \(B {\leq ^{p}_{m}} A\). Fix a polynomial time computable function f such that \(B {\leq ^{p}_{m}} A\) via f where, by A being tally, w.l.o.g. we may assume that f(x) = 1 for all x such that f(x)∉{0}∗. Now, as shown in Ambos-Spies [4], any n2-generic set is incompressible under p-m-reductions. So the function f is almost one-to-one, i.e., there are only finitely many pairs (x,y) of strings such that x≠y and f(x) = f(y). So we may fix n0 such that f is one-to-one on the strings of length ≥ n0, where we can choose n0 so that f(x)≠ 1 (hence f(x) ∈{0}∗) for any string x of length ≥ n0 and that p(n) < 2n for n ≥ n0 where p is a polynomial time bound for f (hence |f(x)| < p(|x|)). But then, for n ≥ n0, |Σn| = |f(Σn)| and f(Σn) ⊆{0m : m < p(n)} hence

$$2^{n} = |{\Sigma}^{n}| = |f({\Sigma}^{n})| \leq |\{0^{m}: m < p(n)\}| = p(n) < 2^{n},$$

which gives the desired contradiction. □

By Theorem 8, in order to distinguish strong E-nontriviality from E-category completeness (and E-measure completeness), it suffices to show that there is a tally strongly E-nontrivial set in E. To do so we use the following observation on Ek+ 1-bi-immune sets.

Lemma 9

LetA ∈E be Ek+ 1-bi-immune(k ≥ 1)and let\(\hat {A}\)bethe length language\(\hat {A} = \{x: 0^{|x|} \in A\}\).Then\(\hat {A} \in \mathrm {E}\),\(\hat {A} {\leq ^{p}_{m}} A\),and\(\hat {A}\)isEk-bi-immune.

Proof

Obviously, \(\hat {A} {\leq ^{p}_{m}} A\) via f(x) = 0|x|. Since |f(x)| = |x| and A ∈E it follows, by Lemma 2, that \(\hat {A} \in \mathrm {E}\) too. It remains to show that \(\hat {A}\) is Ek-bi-immune. By symmetry, it suffices to show that there is no infinite set B ∈Ek such that \(B \subseteq \hat {A}\). For a contradiction assume that such a set B exists. Then, for \(\tilde {B} = \{0^{n}: \exists x \in B (|x|=n)\}\), \(\tilde {B} \in \mathrm {E}_{k + 1}\), \(\tilde {B}\) is infinite and \(\tilde {B} \subseteq A\). So A is not Ek+ 1-bi-immune contrary to assumption. □

Theorem 9

There is a tally setA ∈E which is strongly E-nontrivial.

Proof

Since there are E2-bi-immune sets in E, it follows from Lemma 9 that there is a length language A1 ∈E which is E1-bi-immune. By Theorem 1, A1 is strongly E-nontrivial. Since, for the tally set A = A1 ∩{0}∗, A is in E and A is p-m-equivalent to A1, it follows from p-m-invariance of strong E-nontriviality that A has the desired properties. □

It remains to separate E-nontriviality from strong E-nontriviality. We do this by showing that there are E-nontrivial sets of very low density whereas strongly E-nontrivial sets in E do not have (sufficiently easily recognizable) exponential gaps. These observations will allow us to argue that there are exptally sets in E which are E-nontrivial whereas no such set is strongly E-nontrivial.

In order to prove the existence of E-nontrivial sets of very low density in E, we observe that any sufficiently complex tally set in E is E-nontrivial.

Theorem 10

LetA ∈E ∖E1be tally. Then A is E-nontrivial.

Proof

Given k ≥ 1, it suffices to give a set Bk such that \(B_{k} {\leq ^{p}_{m}} A\) and Bk ∈E ∖Ek. The set Bk is defined as a compressed version of A as follows. For n ≥ 0 let

$$y_{n} = 0^{\lfloor \frac{n}{k + 1} \rfloor}1z_{n}$$

where zn in the n th binary string with respect to the canonical ordering, and let

$$B_{k} = \{y_{n}: n \geq 0 \& 0^{n} \in A\}.$$

In order to show that Bk has the required properties, first note that the strings yn have the following properties.

  1. (i)

    For almost all n, \(\frac {n}{k + 1} \leq |y_{n}| \leq \frac {n}{k}\) (since \(\frac {n}{k + 1} \leq 0^{\lfloor \frac {n}{k + 1} \rfloor }1 \leq \frac {n}{k + 1}+ 1\) and |zn|≈ log(n)),

  2. (ii)

    for a given number n, yn can be computed in poly(n) steps, and

  3. (iii)

    for a given string x, in poly(|x|) steps we can tell whether x = yn for some n and if so compute the unary representation 0n of the unique n with this property.

Now, since yn ∈ Bk if and only if 0n ∈ A, (iii) implies that \(B_{k} {\leq ^{p}_{m}} A\) via f where f(x) = 0n if x = yn and f(x) = 1∉A if x is not among the strings yn, n ≥ 0. Moreover, by the first inequality in (i), |f(x)|≤ (k + 1) ⋅|x| for almost all x whence, by A ∈E and by Lemma 2, Bk ∈E too. Finally, Bk∉Ek. Namely, otherwise, for sufficiently large n, A(0n) can be computed in O(2n) steps (contrary to A∉E1) by first computing yn (which, by (ii), can be done in poly(n) steps) and then computing Bk(yn) (which, by assumption and by the second inequality in (i), can be done in \(O(2^{k \cdot |y_{n}|}) \leq O(2^{n})\) steps). □

Corollary 1

Let B be an infinite tally set such thatB ∈E.There is an E-nontrivialset A in E such thatA ⊆ B.

Corollary 1 is a direct consequence of Theorem 10 and the following observation.

Lemma 10

Let B be any infinite set in E and letk ≥ 1.There is a subset A of B such thatA ∈E ∖Ek.

Proof

This can be shown by a straightforward diagonalization. Alternatively, we can use the fact that, for any k′≥ 1, there is an \(\mathrm {E}_{k^{\prime }}\)-bi-immune set in E. Namely, given k′≥ k such that \(B \in \mathrm {E}_{k^{\prime }}\), let A = B ∩ C where C is any \(\mathrm {E}_{k^{\prime }}\)-bi-immune set in E. Then, obviously, A ⊆ B and, by closure of E under intersection, A ∈E. Finally, by \(\mathrm {E}_{k^{\prime }}\)-bi-immunity of C and by choice of B, \(A = B \cap C \not \in \mathrm {E}_{k^{\prime }}\). So, by k′≥ k, A∉Ek. □

Corollary 1 directly implies that there are exptally E-nontrivial sets in E. Here a set A is exptally if A ⊆{0δ(n) : n ≥ 0} where \(\delta : \mathbb {N} \to \mathbb {N}\) is the iterated exponential function inductively defined by δ(0) = 0 and δ(n + 1) = 2δ(n). (Intuitively, an exptally set may be viewed as the unary encoding of a tally set or as the unary encoding of the unary encoding of an arbitrary set.)

Corollary 2

There is an E-nontrivialset A in E which is exptally.

Proof

Since {0δ(n) : n ≥ 0}∈P, this is immediate by Corollary 1. □

Remark 11

1. It might be of interest to note that Theorem 10 and Corollary 1 in general fail for sparse sets in place of tally sets. A counter example provides the E-trivial set A ∈E constructed in the proof of Theorem 4 which is sparse (in fact contains at most one string of each length). Moreover, the set A constructed there satisfies the condition

$$ \forall^{\infty} x (|f(x)| \leq 2 \cdot |x| \text{ or } f(x) \not\in A) $$

for all polynomial-time computable functions f. Since this property is inherited by any subset of A, it follows by the Boundedness Lemma (Lemma 8) that all subsets of A in the class E are E-trivial too.

2. Similarly, in Theorem 10 and Corollary 1 the assumptions that A ∈ E and B ∈E, respectively, are necessary. The former follows from the observations in the second part of Remark 6. Namely, given a computable time bound t(n) dominating the linear exponential functions 2kn (k ≥ 1) and sets A and B such that B is DTIME(t(n))-hard and (A,B) is a p-m-minimal pair, it holds that A∉E and A is E-trivial. Now, given such a pair (A,B), it suffices to let \(\hat {A} = \{0^{n}: z_{n} \in A\}\) be the unary representation of A. Then \(\hat {A} {\leq ^{p}_{m}} A\) and, by A∉E, \(\hat {A} \not \in \mathrm {P}\). Hence \((\hat {A}, B)\) is a p-m-minimal pair again. So, by the above observation, the tally set \(\hat {A}\) is not in E (hence not in E1) and is E-trivial.

In order to give a counterexample to the generalization of Corollary 1 where the assumption that B is in E is dropped, it suffices to give an infinite tally set B such that

$$ \forall A (A \subseteq B \Rightarrow A \text{ is }\mathrm{E}\text{-trivial}) $$
(13)

holds. Such a set B can be obtained by a rather straightforward finite extension argument. In order to guarantee (13) it suffices to meet the requirements

$$ \Re_{2e}: \text{ If }f_{e_{1}}(E_{e_{0}}) \cap \{0\}^{*} \text{ is infinite then }f_{e_{1}}(E_{e_{0}}) \not\subseteq B. (e = \langle e_{0},e_{1} \rangle) $$

for e ≥ 0 where {Ee}e≥ 0 and {fe}e≥ 0 are computable enumerations of the class E and the class of the polynomial time computable functions, respectively. Note that the requirements R2e, e ≥ 0, guarantee that, for any subset A of B and for any C ∈E such that \(C {\leq ^{p}_{m}} A\), the set C is polynomial time computable, hence A is E-trivial. (Namely, given f such that \(C {\leq ^{p}_{m}} A\) via f, f(C) ⊆ A ⊆ B ⊆{0}∗. So, for indices e0 and e1 such that \(C=E_{e_{0}}\) and \(f=f_{e_{1}}\), requirement \(\Re _{2\langle e_{0},e_{1} \rangle }\) guarantees that f(C) is finite hence C ∈P.) On the other hand, in order to ensure that B is infinite, it suffices to meet the requirements

$$\Re_{2e + 1}: \exists n \geq e (0^{n} \in B)$$

for e ≥ 0.

The construction of B is as follows. At stage s + 1 - where l(s) ≥ 0 and \(B \upharpoonright l(s) = B \cap {\Sigma }^{< l(s)}\) have been defined previously (where l(0) = 0) - l(s + 1) > l(s) and the finite extension \(B \upharpoonright l(s + 1)\) of \(B \upharpoonright l(s)\) are defined as follows thereby guaranteeing that requirement Rs is met. If s = 2〈e0,e1〉 then let l(s + 1) = |x| + 1 for the least \(x \in f_{e_{1}}(E_{e_{0}}) \cap \{0\}^{*}\) such that l(s) ≤|x| if there is such an x, let l(s + 1) = l(s) + 1 otherwise, and - in either case - let \(B \upharpoonright l(s + 1) = B \upharpoonright l(s)\). If s = 2e + 1 then let l(s + 1) = l(s) + 1 and let \(B \upharpoonright l(s + 1) = (B \upharpoonright l(s)) \cup \{0^{l(s)}\}\).

Note that the above given construction of B is not effective, hence B is not computable. A computable set B with the above properties can be obtained by a more sophisticated diagonalization argument using the speed-up technique of [2].

In order to show that Corollary 2 fails if we replace E-nontriviality by strong E-nontriviality we prove a stronger result, namely we show that a strongly E-nontrivial set in E does not have infinitely many E-recognizable gaps of exponential size.

Theorem 12

Let A and B be sets in E such thatB ⊆{0}∗, B is infinite, and

$$ \forall n (0^{n} \in B \Rightarrow A \cap \{x: n < |x| < 2^{n}\} = \emptyset) $$
(14)

holds. Then A is not strongly E-nontrivial.

Proof

By A,B ∈E fix k ≥ 1 such that A,B ∈Ek. It suffices to show that there is no Ek-bi-immune set (in E) which can be p-m-reduced to A. So, given any set D ∈Pm(A), in order to show that D is not Ek-bi-immune fix f such that \(D {\leq ^{p}_{m}} A\) via f and, by polynomial time computability of f , fix n0 such that |f(x)| < 2|x| for all strings x of length > n0. Since the tally set B is infinite and in Ek, it suffices to show that, for n > n0 such that 0n ∈ B, D(0n) can be computed in O(2kn) steps. (Namely, if so, D ∩ B and \(\overline {D} \cap B\) are in Ek. So, by infinitiy of B, D ∩ B is an infinite Ek-subset of D or \(\overline {D} \cap B\) is an infinite Ek-subset of \(\overline {D}\), and either implies that D is not Ek-bi-immune.) Since f is polynomial time computable and since D(0n) = A(f(0n)), for n such that |f(0n)|≤ n, this follows from A ∈Ek, while, for n such that |f(0n)| > n, A(f(0n)) = 0 by (14). □

Since, for any exptally set A, (14) holds for the polynomial time computable set B = {0δ(n) : n ≥ 0}, it follows from Theorem 11 that no exptally set in E is strongly E-nontrivial.

Corollary 3

LetA ∈E be exptally. Then A is not strongly E-nontrivial.

Theorem 11 implies that many constructions (of sets in E) in the theory of the polynomial-time degrees which are based on so-called gap languages (see e.g. Section 3 of [5]) yield sets which are not strongly E-nontrivial. We will come back to this in the next section.

Note that, by a straightforward diagonalization, there is an exptally set A ∈E ∖E1. So, by Corollaries 2 and 3, there is an E-nontrivial set in E which is not strongly E-nontrivial:

Corollary 4

There is an E-nontrivialset A in E which is weakly E-trivial.

The above density results give the desired separations of the weak completeness notions.

Theorem 13

For any set A the following hold.

$$ \begin{array}{@{}rcl@{}} &&A \mathrm{E}\text{-hard}\\ && \Downarrow\\ &&A \mathrm{E}\text{-measure hard}\\ && \Downarrow\\ &&A \mathrm{E}\text{-category hard}\\ && \Downarrow\\ &&A \text{strongly} \mathrm{E}\text{-nontrivial}\\ && \Downarrow\\ &&A \mathrm{E}\text{-nontrivial}\\ && \Downarrow\\ &&A \text{intractable} \end{array} $$
(15)

Moreover all implications are strict and witness sets A for strictness can be foundin E.

Proof

By Lemma 3 it suffices to give witness sets A ∈E for the strictness of the implications.

Strictness of the first implication (from top) holds by Lutz [18] where it has been shown that there are E-measure complete sets which are not E-complete while strictness of the fifth implication follows from the existence of intractable E-trivial sets in E which we have established in Section 3.

Strictness of the second implication follows from the fact that E-measure complete sets are exponentially dense (Theorem 7 due to Mayordomo and Lutz) whereas there are sparse E-category complete sets (Theorem 8).

Strictness of the third implication follows from the fact that no E-category complete set is tally (Theorem 8) whereas there are tally strongly E-nontrivial sets (Theorem 9).

Finally, strictness of the fourth implication follows from the fact that no strongly E-nontrivial set is exptally (Theorem 3) whereas there are exptally E-nontrivial sets (Corollary 2). □

5 On the Information Content of E-Nontrivial and Strongly E-Nontrivial Sets

In the preceding section we have distinguished E-nontriviality from the stronger weak completeness notions for E by analysing the possible densities of sets with these properties. Here we present another difference in the sense of information content. We look at the following question: If we split a weakly complete set A into two parts A0 and A1, is at least one of the parts weakly complete again? As we will show, for E-nontriviality the answer is YES whereas for the other weak completeness notions the answer is NO. Moreover, if we split a complete set into two parts where one of the parts is E-trivial then the other part is complete.

In order to make our question more precise we need the following notion. A splitting of a set A into two disjoint sets A0 and A1 is a p-splitting if there is a set B ∈P such that A0 = A ∩ B and \(A_{1} = A \cap \overline {B}\). Note that, for a p-splitting (A0,A1) of A, \(A_{0}, A_{1} {\leq ^{p}_{m}} A\) and \(A {\equiv ^{p}_{m}} A_{0} \oplus A_{1}\) where A0 ⊕ A1 is the effective disjoint union {0x : x ∈ A0}∪{1y : y ∈ A1} of A0 and A1. So, intuitively, a p-splitting decomposes a problem A into two subproblems A0 and A1 so that for solving A it suffices to solve A0 and A1.

Now Ladner [16] has shown that any computable intractable set A can be p-split into two lesser intractable problems, i.e., into problems A0,A1∉P such that \(A_{0}, A_{1} <^{p}_{m} A\). So, in particular, any E-complete set A can be p-split into two incomplete sets. In fact, by analysing Ladner’s proof, the set B ∈P defining the p-splitting (A0,A1) of A is a gap language, i.e., B and \(\overline {B}\) have infinitely many polynomial time recognizable gaps of exponential length. Hence, by Theorem 11, we obtain the following stronger result from Ladner’s proof.

Theorem 14

LetA ∈E ∖P.There is a p-splitting of A into setsA0,A1∉P such thatA0andA1are weakly E-trivial.

So, in particular, any E-complete (E-measure complete, E-category complete, strongly E-nontrivial) set A has a p-splitting into sets A0 and A1 which are not E-complete (not E-measure complete, not E-category complete, weakly E-trivial, respectively). For E-nontriviality, however, the corresponding fact fails.

Theorem 15

Let A be E-nontrivialand let (A0,A1) be a p-splitting of A. ThenA0is E-nontrivialorA1is E-nontrivial(or both).

Proof

The key to the proof is the trivial observation that, for a p-splitting (C0,C1) of a set C∉Ek, C0∉Ek or C1∉Ek.

Fix B ∈P such that A0 = A ∩ B and \(A_{1} = A \cap \overline {B}\), and, for a contradiction, assume that A0 and A1 are E-trivial. By the latter, we may fix a number k such that

$$ \forall i \leq 1 [\mathrm{P}_{m}(A_{i}) \cap \mathrm{E} \subseteq \mathrm{E}_{k}]. $$
(16)

On the other hand, by E-nontriviality of A, we may fix a set C ∈E ∖Ek such that \(C {\leq ^{p}_{m}} A\) and a polynomial time computable function f such that \(C {\leq ^{p}_{m}} A\) via f.

Then, for D = {x : f(x) ∈ B}, D ∈P. So we may consider the p-splitting (C0,C1) given by D, i.e., C0 = C ∩ D and \(C_{1} = C \cap \overline {D}\). By C ∈E and D ∈P, it holds that C0,C1 ∈E. Moreover, \(C_{0} {\leq ^{p}_{m}} A_{0}\) and \(C_{1} {\leq ^{p}_{m}} A_{1}\) via f0 and f1, respectively, where

$$ f_{0}(x) = \left\{\begin{array}{llll} f(x) & \text{if } x \in D\\ y_{0} & \text{otherwise} \end{array}\right. \text{ and } f_{1}(x) = \left\{\begin{array}{lll} f(x) & \text{if } x \not\in D\\ y_{0} & \text{otherwise} \end{array}\right. $$

for a fixed string y0∉A. So Ci ∈Pm(Ai) ∩E (i = 0,1), hence C0,C1 ∈Ek by (16). But this contradicts the observation on p-splittings preceding the proof, namely that, by C∉Ek, C0∉Ek or C1∉Ek. □

For an E-complete set A we obtain the following strengthening of Theorem 15. For any p-splitting (A0,A1) of A such that A0 is E-trivial, the splitting cannot be proper, i.e., A1 will be E-complete. (So E-trivial sets do not help for computing E-complete sets.) Note that this is immediate by the following slightly more general result.

Theorem 16

Let A and B be computable sets such thatA ∈E is E-trivialand B is not E-hard.ThenA ⊕ Bis not E-hard.

The proof of Theorem 16 is based on the following observation on the distribution of the Ek-bi-immune sets in E which might be of interest for its own sake.

Lemma 11

Letk ≥ 1 and let A be any computable set such that A is notE-hard.Then there is an Ek-bi-immuneset B in E such that\(B {\not \leq ^{p}_{m}} A\)andA ⊕ Bis not E-hard.

Proof

By a delayed diagonalization we will construct a set B with the required properties in stages where at stage s of the construction the value B(zs) is determined.

Fix some E-complete set C in E1, let {fe}e≥ 0 be a computable enumeration of the class of the polynomial time computable functions such that fe(x) can be uniformly computed in time 2max(e,|x|), and let \(\{{E^{k}_{e}}\}_{e \geq 0}\) be a computable enumeration of the class Ek such that \({E^{k}_{e}}(x)\) can be uniformly computed in time 2(k+ 2) max(e,|x|).

Then it suffices to ensure that B ∈Ek+ 3 and that B meets the requirements

$$ \Re_{4e}:B \text{ is not } p-m-\text{ reducible to } A \text{ via } f_{e} $$
$$ \Re_{4e + 1}:C \text{ is not }p-m-\text{ reducible to }A \oplus B \text{ via } f_{e} $$
$$ \Re_{4e + 2}: \mathrm{E}^{k}_{e} \text{ is infinite} \Rightarrow B \cap \mathrm{E}^{k}_{e} \neq \emptyset $$
$$ \Re_{4e + 3}: \mathrm{E}^{k}_{e} \text{ is infinite} \Rightarrow \bar{B} \cap \mathrm{E}^{k}_{e} \neq \emptyset $$

for all e ≥ 0. Namely the requirements R4e ensure that that B is not p-m-reducible to A, the requirements R4e+ 1 ensure that A ⊕ B is not E-hard, and the requirements R4e+ 2 and R4e+ 3 ensure that B is Ek-bi-immune.

The idea for meeting requirement R4e is to let B look like C on a sufficiently large interval where the interval is only closed when by looking back a disagreement B(x)≠A(fe(x)) is found. (Note that eventually there must be such a disagreement since otherwise \(B {\leq ^{p}_{m}} A\) via fe and B =∗C, hence \(C {\leq ^{p}_{m}} A\) contrary to the assumption that A is not E-hard.) Similarly, the idea for meeting requirement R4e+ 1 is to let B look like the empty set on a sufficiently large interval where now the interval is only closed when a disagreement C(x)≠A ⊕ B(fe(x)) is found. (Note that eventually there must be such a disagreement since otherwise \(C {\leq ^{p}_{m}} A \oplus B\) and B is finite. So, again, \(C {\leq ^{p}_{m}} A\) contrary to the assumption that A is not E-hard.)

We now describe stage s of the construction at which B(zs) is defined. We look at the requirements Rn with n ≤ s where some of these requirements may have been declared satisfied at a previous stage.

  • For i ≤ 1 we say that requirement R4e+i requires attention at stage s if

    1. (i)

      4e + i ≤ s and R4e+i has not yet been declared satisfied

    and, for 2 ≤ i ≤ 3, we say that requirement R4e+i requires attention at stage s if (i) holds and

    1. (ii)

      \(z_{s} \in \mathrm {E}^{k}_{e}\).

    Then fix n = 4e + i (i ≤ 3) minimal such that Rn requires attention. (If there is no such n then let B(zs) = 0 and go to stage s + 1.) Declare that Rn is active at stages.

    For the definition of B(zs) distinguish the following cases:

    $$ B(z_{s}) = \left\{\begin{array}{ll} C(z_{s}) & \text{ if } i = 0 \\ 0 & \text{ if } i = 1\text{ or } i = 3 \\ 1 & \text{ if } i = 2. \end{array}\right. $$

    Finally, if i ≥ 2 then the active requirement R4e+i is declared satisfied at stage s + 1. If i = 0 then, for up to |zs| steps, try to find out whether there is a string x < zs such that B(x)≠A(fe(x)) and 2|x| < |zs| (where the strings x are checked in order); and if such an x is found then declare requirement R4e to be satisfied at stage s. If i = 1 then for up to |zs| steps try to find out whether there is a string x < zs such that C(x)≠A ⊕ B(fe(x)), 2|x| < |zs| and fe(x) < zs; and if such an x is found then declare requirement R4e+ 1 to be satisfied at stage s.

This completes the construction.

In order to show that the set B has the required properties, first note that, given s, B(z0),…,B(zs− 1), and the indices of the requirements \(\Re _{n^{\prime }}\) which have been declared satisfied prior to stage s, in a total of \(O(2^{(k + 2)|z_{s}|})\) steps we can 1) compute the index n of the requirement Rn which becomes active at stage s (if any), 2) compute B(zs), and 3) decide whether requirement Rn is declared satisfied at stage s. So, by induction, B ∈Ek+ 3. Hence it suffices to show that all requirements are met. This is established as follows. □

Claim 1

Requirement Rn requires attention at most finitely often.

Proof

The proof is by induction on n. By inductive hypothesis, fix a stage s0 ≥ n such that no requirement \(\Re _{n^{\prime }}\) with n′ < n requires attention after stage s0. Then requirement Rn becomes active at any stage s > s0 at which it requires attention. So it suffices to show that Rn becomes active during at most finitely many stages s > s0. In order to show this let n = 4e + i (i ≤ 3) and distinguish the following cases according to the value of i.

If i ≥ 2 then the claim is immediate since a requirement R4e+i of this type which becomes active at a stage s is declared satisfied at stage s hence will not require attention after stage s.

This leaves the cases i = 0 and i = 1. Here, for a contradiction, assume that requirement R4e+i becomes active at infinitely many stages. Then R4e+i is never declared satisfied, hence, by construction and by choice of s0, R4e+i requires attention and becomes active at all stages s > s0.

So, for i = 0, B(zs) = C(zs) for s ≥ s0, and there is no string x such that B(x)≠A(fe(x)) since otherwise, at a sufficiently large stage s > s0, the least such x will be found and requirement R4e+i will be declared satisfied. It follows that C =∗B and \(B {\leq ^{p}_{m}} A\) via fe, hence \(C {\leq ^{p}_{m}} A\). But, by E-completeness of C, this implies that A is E-hard contrary to choice of A.

Similarly, for i = 1, B(zs) = 0 for s ≥ s0, and we can argue that there is no string x such that C(x)≠A ⊕ B(fe(x)). It follows that B is finite and \(C {\leq ^{p}_{m}} A \oplus B\) hence \(C {\leq ^{p}_{m}} A\). So, again, A is E-hard contrary to choice of A. □

Claim 2

Requirement Rn is met.

Proof

For a contradiction assume that Rn is not met. Then, as one can easily show, requirement Rn is never satisfied and requires attention infinitely often contrary to Claim 1. We show this for n = 4e and leave the other cases to the reader.

Note that if requirement R4e is declared satisfied at some stage s then B(x)≠A(fe(x)) for some x, hence R4e is met. So, by assumption, R4e is never declared to be satisfied. But, by construction, this implies that R4e requires attention at all stages s ≥ 4e.

This completes the proof of Lemma 11. □

Proof

(of Theorem 16) Given an E-trivial set A in E and a computable set B which is not E-hard, for a contradiction assume that A ⊕ B is E-hard. By E-triviality of A, fix k ≥ 1 such that

$$ \mathrm{P}_{m}(A) \cap \mathrm{E} \subseteq \mathrm{E}_{k} $$
(17)

holds. Then, by Lemma 11 (applied to k and B), there is an Ek-bi-immune set C in E such that \(C {\not \leq ^{p}_{m}} B\). On the other hand, by E-hardness of A ⊕ B, \(C {\leq ^{p}_{m}} A \oplus B\), say via f. Then, for D = {x : f(x) ∈Σ∗⊕∅}, D ∈P, C ∩ D ∈E, \(C \cap \overline {D} \in \mathrm {E}\), \(C \cap D {\leq ^{p}_{m}} A\) and \(C \cap \overline {D} {\leq ^{p}_{m}} B\).

Now distinguish the following two cases. First assume that C ∩ D is infinite. Then, by Ek-bi-immunity of C, C ∩ D∉Ek. But, since C ∩ D ∈Pm(A) ∩E, this contradicts (17). This leaves the case that C ∩ D is finite. But then \(C {\equiv ^{p}_{m}} C \cap \overline {D}\), hence \(C {\leq ^{p}_{m}} B\) contrary to choice of C. □

6 Further Results

We conclude with a short summary of some other results on our new weak completeness notions which appeared somewhere else.

Comparing Weak Hardness for E and EXP.:

While, by a simple padding argument, E-hardness and EXP-hardness coincide, Juedes and Lutz [15] have shown that E-measure hardness implies EXP-measure hardness whereas the converse in general fails. Moreover, by using similar ideas, the corresponding results have been obtained for category hardness (see [4]).

Now we can easily adapt the concepts of (strong) nontriviality for E to the polynomial-exponential time class EXP by replacing E and Ek in the definitions by EXP and EXPk, respectively. Then, the arguments of [15] can be easily duplicated to show that strong E-nontriviality implies strong EXP-nontriviality but in general not vice versa.

For clarifying the relations between E-nontriviality and EXP-nontriviality, however, the above arguments fail and new much more sophisticated techniques have to be employed. As it turns out, in contrast to the above results, E-nontriviality and EXP-nontriviality are independent. I.e. neither E-nontriviality implies EXP-nontriviality nor EXP-nontriviality implies E- nontriviality. For details see [8].

Weak Hardness Under Weak Reducibilities. :

The classical approach to generalize hardness notions is to generalize (weaken) the reducibilities underlying the hardness concepts, i.e., to allow more flexible codings in the reductions. So Watanabe [20] has shown that weaker reducibilities than p-m-reducibility like p-btt-reducibility (bounded truth-table), p-tt-reducibility (truth-table) and p-T-reducibility (Turing) yield more E-complete sets. For measure-completeness and category-completeness similar results have been shown in [9] (for both E and EXP). For strong nontriviality we obtain the corresponding results, i.e., a complete separation of p-m, p-btt, p-tt, and p-T (for both E and EXP), by fairly standard methods. For nontriviality, however, the separations of E-nontriviality under p-m, p-btt, p-tt, and p-T reducibilities require some quite involved and novel speed-up diagonalization technique. The reason why standard methods fail in this setting might be explained by the fact that - in contrast to all of the just mentioned separation results - EXP-nontriviality under p-m, p-btt, and p-tt coincide. See [7] for details.