The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 24 NO.5 / (1995))
With Quasilinear Queries Exp is not Polynomial Time Turing Reductible to Sparse Sets
Bin Fu,
Pages. 1082-1090
Abstract 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 E=DTIME$(2^{O(n)})$ and EXP=DTIME$(2^n^{O(n)})$, the following
results are shown in this paper: (1) For any $a<1$, every EXP-$leq^p_{n^a-T}$-hard set is exponentially dense. This yields
EXP$
otsubseteq$P$_{n^a-T}$(SPARSE) for all $a<1$. (2) For any $a<frac{1}{2}$, every E-$leq^p_{n^a-T}$-hard set is exponentially dense. (3) E$
otsubseteq$P$_{o(n/log n)-T}$(TALLY). Our results substantially improve Watanabe's earlier theorem, E$
otsubseteq$P$_{log n-tt}$(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].
Contents 1. Introduction
2. Preliminaries
3. Number of queries and density
Key words exponential time complexity classes, polynomial time Turing reducibilities, spare sets.
Mathmatical Subject Classification 68Q15