Sparse Sets in NP-P: EXPTIME Versus NEXPTIME
Hartmanis, Juris; Sewelson, Vivian; Immerman, Neil
This paper investigates the structural properties of sets in NP-P and shows that the computational difficulty of lower density sets in NP depends explicitly on the relations between higher deterministic and nondeterministic time-bounded complexity classes. The paper exploits the recently discovered upward sparation method, which shows for example that there exist sparse sets in NP-P if and only if EXPTIME $\neq$ NEXPTIME. In addition, the paper uses relativization techniques to determine logical possibilities, limitations of these proof techniques, and, for the first time, to exhibit structural differences between relativized NP and CoNP.
computer science; technical report
Previously Published As