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

  • $\begingroup$ 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 $\endgroup$ – vzn Jun 24 '15 at 17:17
  • $\begingroup$ @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. $\endgroup$ – Ari Jun 24 '15 at 17:59
  • $\begingroup$ 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... $\endgroup$ – 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.

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

| cite | improve this answer | |
  • $\begingroup$ it sounds like you nearly sketched out a proof that P≠NP. ie the question is close to asking whether P≠NP wrt existence of a "particular" NPI language, which is "nearly" equivalent. ie NP≠NPI is not proven. $\endgroup$ – vzn Jun 24 '15 at 20:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.