Nontriviality for exponential time w.r.t. weak reducibilities

A set A is nontrivial for the linear exponential time class if and the sets from which can be reduced to A are not from a single level of the linear exponential hierarchy. Similarly, a set A is nontrivial for the polynomial exponential time class if and the sets from which can be reduced to A are not from a single level of the polynomial exponential hierarchy (see [2]). Here we compare the strength of the nontriviality notions with respect to the underlying reducibilities where we consider the polynomial-time variants of many–one, bounded truth-table, truth-table, and Turing reducibilities. Surprisingly, the results obtained for and differ. While the above reducibilities yield a proper hierarchy of nontriviality notions for , nontriviality for under many–one reducibility and truth-table reducibility coincides.