# Constructing languages in NPI other than through Ladner's Theorem

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.)

• NPI is conjectured to be "larger" than P just as P≠NP. did you mean to ask if the intersection is in NPI? if P≠NP then there are no NP complete sparse languages and the intersection (of NP complete languages with sparse larguages) must be empty. suggest further discussion in TCS chat – vzn Jun 24 '15 at 17:17
• @vzn Sorry if my question was unclear. I meant to ask if the intersection of a sparse language and an NP-complete set is definitely known to be in NPI (assuming P != NP). I know that it cannot be NP-complete by Mahaney's theorem and assume that it cannot be in P (but I don't know how to prove the latter or if anyone has). I'll edit the question. – Ari Jun 24 '15 at 17:59
• what you describe would nearly be a P≠NP proof... ie basically an open/ research problem... it looks like the below answer by YF is now not based on your latest edit which changes the question significantly... – vzn Jun 24 '15 at 20:10

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.