On lower bounds of the closeness between complexity classes

We show that if an NP-m-hard set is the union of a set in P_btt(Sparse) and the setA, then NP P_dtt(A). Since co-NP, R, and FewP are closed under _dtt ^P -reductions, so no NP-m-hard set is the union of a set in P_btt(Sparse) and a set in co-NP (resp. R, FewP) unless NP = co-NP (resp. NP = R, NP = FewP). We also study the distance between many important complexity classes. LetA,B be two sets. The distance function dist _A,B is defined as in S1] such that dist _A,B (n) is the number of strings of length n inA B = (A – B) (B – A). We show that there exists a setA in p_{(k + 1)–tt}(Sparse) such that, for everyB in P _k–tt(Sparse), dist _A,B has an exponential lower bound.This research was supported in part by HTP 863.