Sparse sets and collapse of complexity classes

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.