Sparse Sets and Collapse of Complexity Classes

AbstractIn 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)≠NTIME(F) can be characterized by the existence of (not only polynomially) sparse 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 nO(log n)–sparse set in NP−P iff ∪c>1NTIME(2c□n)≠∪c>1DTIME(2c□n). Further we prove that there is an nO(log n)–sparse set in NP−coNP iff ∪c>1NTIME(2c□n)≠∪c>1coNTIME(2c□n). The technique also allows us to characterize the existence of sets of different 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 nO(log n)–sparse set in NP−P iff there is an nO((log n)3)–sparse set in ∪c>1NTIME(nclog n)−∪c>1DTIME(nclog n). The end of the paper is devoted to limitations of the technique