Weak completeness notions for exponential time

DOI10.1007/S00224-019-09920-4MaRDI QIDQ2322715zbMATH OpenOpenAlexWikidataFDO

Authors Timur Bakibayev, Klaus Ambos-Spies

Publication date 5 September 2019

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL http://archiv.ub.uni-heidelberg.de/volltextserver/10499/1/thesis.pdf

almost everywhere complexity completeness exponential time linear exponential time reductions resource-bounded measure weak completeness

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Review text

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.

Recommendations

Cites work

Cited in

(11)

This page was built for publication: Weak completeness notions for exponential time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2322715)