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.