Can intersection of two languages in NP which are not NP complete be NP complete?

Can intersection of two languages in coNP which are not coNP complete be coNP complete?

Can intersection of two languages one in coNP but not complete and other in NP but not NP complete be NP complete or coNP complete?

  • $\begingroup$ Very interesting. :) $\endgroup$ Dec 10, 2015 at 5:27
  • 2
    $\begingroup$ If P=NP, then the answer is NO. In this case the only languages that are not NP-complete (coNP-complete) are the empty set and $\Sigma^*$. $\endgroup$
    – Gamow
    Dec 10, 2015 at 9:54
  • 3
    $\begingroup$ If P is not equal to NP the by ladners thm NP intermidiate problems do exist...any example you would suggest of a natural. One. $\endgroup$
    – ARi
    Dec 10, 2015 at 10:29

1 Answer 1


Just an extended comment to better explain ARi's comment (I was writing it while I saw it).

It is sufficient to use a "large gap" approach similar to the one used in Lardner's theorem; for example:

$A_1 = \{ x \mid x \in SAT \land f(|x|) \text { is even}\} \cup \{x \mid f(|x|) \text{ is odd} \}$

$A_2 = \{ x \mid x \in SAT \land f(|x|) \text { is odd}\} \cup \{x \mid f(|x|) \text{ is even} \}$

Where $f$ is a slow enough increasing function computable in polynomial time. See for example its construction in Ladner's theorem proof in Appendix A.1 of Uniformly Hard Languages.

By construction $A_1, A_2$ are not NPC, but $A_1 \cap A_2 = SAT$

  • 2
    $\begingroup$ why are $A_1$ and $A_2$ not NPC? $\endgroup$ Dec 10, 2015 at 14:38
  • $\begingroup$ @MateusdeOliveiraOliveira: by delayed diagonalization $\{ x \mid x \in SAT \land f(|x|) \text{ is even}\}$ is not NPC ($A_1$ is an artificial NP-intermediate problem); see the linked proof for details. Of course, we must assume that $P \neq NP$; the $P = NP$ case has already been ruled out by Gamow in the comment above. $\endgroup$ Dec 10, 2015 at 15:42
  • $\begingroup$ Cant f be jsust about any polytime function? $\endgroup$
    – ARi
    Dec 11, 2015 at 7:35
  • $\begingroup$ @ARi: no, it must be slow enough to create large gaps to prevent NP-completeness (to allow delayed diagonalization). I'll try to write a formal proof in the next days. $\endgroup$ Dec 11, 2015 at 7:56
  • $\begingroup$ @MarzioDeBiasi I see. The function $f$ is carefully constructed by the delayed diagonalization method. Thanks. $\endgroup$ Dec 11, 2015 at 8:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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