With Quasilinear Queries EXP Is Not Polynomial Time Turing Reducible to Sparse Sets
Bin Fu · SIAM Journal on Computing · 1995
We investigate the lower bounds of queries required by the polynomial time Turing reductions from exponential time classes to the sets of small density. For complexity classes ${\text{E}} = {\text{DTIME}}(2^{O(n)})$ and ${\text{EXP}} = {\text{DTIME}}(2^{n^{O(1)} } )$, the following results are shown in this paper: (1) For any $a < 1$, every ${\text{EXP-}}\leq _{n^a - {\text{T}}}^{\text{P}}$-hard set is exponentially dense. This yields ${\text{EXP}} subseteq {\text{P}}_{n^{a} - {\text{T}}} ({\text{SPARSE}})$ for all $a < 1$. (2) For any $a < \frac {1}{2}$, every ${\text{E-}}\leq _{n^{a} - {\text{T}}}^{\text{P}}$-hard set is exponentially dense. (3) ${\text{E}} subseteq {\text{P}}_{o({n/\log n}) - {\text{T}}} ({\text{TALLY}})$. Our results substantially improve Watanabe’s earlier theorem, ${\text{E}} subseteq {\text{P}}_{\log n - tt} ({\text{SPARSE}})$ [Proc. 2nd IEEE Conference on Structure in Complexity Theory, 1987, pp. 138–146], [Proc. 7th IEEE Conference on Structure in Complexity Theory, 1992, pp. 222–238].