8
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Very interesting. :) $\endgroup$ – Michael Wehar Dec 10 '15 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 '15 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 '15 at 10:29
19
$\begingroup$

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$

$\endgroup$
  • 2
    $\begingroup$ why are $A_1$ and $A_2$ not NPC? $\endgroup$ – Mateus de Oliveira Oliveira Dec 10 '15 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$ – Marzio De Biasi Dec 10 '15 at 15:42
  • $\begingroup$ Cant f be jsust about any polytime function? $\endgroup$ – ARi Dec 11 '15 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$ – Marzio De Biasi Dec 11 '15 at 7:56
  • $\begingroup$ @MarzioDeBiasi I see. The function $f$ is carefully constructed by the delayed diagonalization method. Thanks. $\endgroup$ – Mateus de Oliveira Oliveira Dec 11 '15 at 8:42

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.