Weak completeness notions for exponential time (Q2322715)

In the present paper, the authors investigate reduction notions that can be employed in the context of linear exponential time (E). It is well known that the complexity class E is not closed under polynomial many-to-one reductions (Lemma 1) through a padding argument. Because of that, \textit{J. H. Lutz} [SIAM J. Comput. 24, No. 6, 1170--1189 (1995; Zbl 0845.68048)] formalised in a way a type of measure for that class. The authors introduce two weak hardness notions for E, namely, (strong) E-nontriviality. Intuitively, a subclass of E is negligible if it is contained in some \(\mathrm{E}_k= \mathrm{DTIME}(2^{kn})\) in the exponential-time hierarchy. Arguing that ``E-nontriviality is the most general weak hardness notion for E'', the authors stress that it ``generalised 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 strong variant of this concept lies strictly between the weak notion and the ones of measure- and category-hardnesses. The authors give a verbose overview of the sections in the introduction and motivate quite well. Section 2 then handles the new central notions and Lemma 3 is an important result showing how meaningful their approach is. Theorem 1 characterises the strong variant via \(\mathrm{E}_1\)-bi-immune sets (a set \(A\) is \(C\)-bi-immune for a class \(C\) if there is no infinite \(B\in C\) such that \(B\subseteq A\) or \(B\cap A=\emptyset\)). Section 3 provides then some examples. First, the existence of an E-trivial set in \(\mathrm{E}\setminus \mathrm{P}\) (Theorem 2), but also E-trivial sets in arbitrarily high levels \(\mathrm{E}\setminus \mathrm{E}_k\) of the E-hierarchy (Theorem 4). Section 4 considers sparse and tally sets in this context. The authors show the existence of an E-category-complete set which is sparse and that no such set is tally (Theorem 8). Yet, there are tally sets which are strongly E-nontrivial (Theorem 9). The authors show the context when tally sets are E-nontrivial (Theorem 10) and when even an E-nontrivial set is exptally (Corollary 2) which is also not strongly E-nontrivial (Corollary 3). Theorem 13 then gives the context for a set \(A\) to be E-hard, E-measure-hard, E-category-hard, strongly E-nontrivial, E-nontrivial, and intractable (in this order). Section 5 talks about information content. Can one, from splitting ``a weakly complete set \(A\) into two parts \(A_0\) and \(A_1\)'', deduce weak completeness for either of them? The authors show that this is true for E-nontriviality but for the remainder of the weak completeness notions this is false.