Abstract: | A set A is nontrivial for the linear-exponential-time class E=DTIME(2
lin
) if for any k≥1 there is a set B
k
∈E such that B
k
is (p-m-)reducible to A and Bk ? DTIME(2k·n)B_{k} \not\in \mathrm{DTIME}(2^{k\cdot n}). I.e., intuitively, A is nontrivial for E if there are arbitrarily complex sets in E which can be reduced to A. Similarly, a set A is nontrivial for the polynomial-exponential-time class EXP=DTIME(2
poly
) if for any k≥1 there is a set ^(B)]k ? EXP\hat{B}_{k} \in \mathrm {EXP} such that ^(B)]k\hat{B}_{k} is reducible to A and ^(B)]k ? DTIME(2nk)\hat{B}_{k} \not\in \mathrm{DTIME}(2^{n^{k}}). We show that these notions are independent, namely, there are sets A
1 and A
2 in E such that A
1 is nontrivial for E but trivial for EXP and A
2 is nontrivial for EXP but trivial for E. In fact, the latter can be strengthened to show that there is a set A∈E which is weakly EXP-hard in the sense of Lutz (SIAM J. Comput. 24:1170–1189, 11) but E-trivial. |