We introduce the notion of p-separability in analogy with the recursion-theoretic notion of recursive separability. The existence of p-inseparable sets in NP is related to structural properties of complexity classes. Sparseness is related to p-separability and structural conditions for the existence of sparse p-inseparable sets NP are given. Using the notion we obtain sets hard for the $\sum_{2}^{0}$ and $\prod_{2}^{0}$ levels of the Kleene Arithmetic Hierarchy. Some independence results are shown to follow.