Constructing languages in NPI other than through Ladner's Theorem

Question

I have seen proofs of Ladner's theorem which detail the construction of languages in NPI assuming P $\neq$ NP. However, I was wondering if there are any other constructions using the fact that sparse sets cannot be NP-complete assuming P $\neq$ NP (Mahaney's Theorem). Specifically, is it definite (assuming P $\neq$ NP) that the intersection of an infinite decidable sparse set and an NP-complete language lies in NPI? It seems to me that it cannot be in P, but I don't know how to prove it. (Note: I am asking about taking a given NP-complete language and its intersection with a sparse set, not about $\textsf{NPC} \cap \textsf{SPARSE}$ which must be empty, again by Mahaney's Theorem.)

Answer 1

It is perfectly possible that the intersection of an infinite decidable sparse set and an NP-complete set lies in P. Take your favorite NP-complete set $L$, and consider $L' = 0L \cup 1^*$, which is still NP-complete. The intersection of $L'$ with the infinite decidable sparse set $1^*$ is $1^*$, which is certainly in P.

Mahaney's theorem shows that sparse sets cannot be NP-complete, but to construct an NPI language you will need to show that your sparse set is not in P, which will probably require diagonalization. Your diagonalization will somehow have to ensure that the resulting language is sparse, while still being in NP and outside of P. Perhaps this can be done, but I'm not aware of any such proof. (That said, my knowledge of the relevant literature is sparse.)