In this paper a new upward separation technique is developed. It is applied
to prove that for a class of functions F a separation DTIME(F) not equal N
TIME(F) can be characterized by the existence of (not only polynomially) sp
arse sets in certain complexity classes. As a consequence, a solution of an
open question of J. Hartmanis (1983, Inform. Process. Lett, 16, 55-60) is
obtained: There is an n(O(log n))-sparse set in NP-P iff
boolean OR (c >1) NTIME (2(2c rootn)) not equal boolean OR (c >1) DTIME (2(
c rootn))
Further he prove that there is an n0 109'1-sparse set in NP - coNP iff
boolean OR (c >1) NTIME (2(c rootn)) not equal boolean OR coNTIME (2(c root
n)).
The technique also allows us to characterize the existence of sets of diffe
rent densities in NP - P by the existence of slightly denser sets in NTIME(
F) - DTIME(F) for certain classes of functions F. For example, there is an
n(O(log) (n))-sparse set in NP - P iff there is an n(O((log n)3))-sparse se
t in
boolean OR (c >1) NTIME (n(c) (log n)) - boolean OR (c >1) DTIME (n(c log n
)).
The end of the paper is devoted to limitations of the technique. (C) 2001 A
cademic Press.