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

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

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

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

<p>Where $f$ is a slow enough increasing function computable in polynomial time. See for example its construction in Ladner's theorem proof in <a href="http://www.cs.umd.edu/~gasarch/COURSES/652/S14/uniform.pdf" rel="noreferrer">Appendix A.1 of Uniformly Hard Languages</a>.</p>

<p>By construction $A_1, A_2$ are not NPC, but $A_1 \cap A_2 = SAT$</p>

CC BY-SA 3.0
2015-12-10T14:38:14.793Z
why are $A_1$ and $A_2$ not NPC?
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2015-12-10T15:42:59.310Z
@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.
Marzio De Biasi
CC BY-SA 3.0
2015-12-11T07:35:36.123Z
Cant f be jsust about any polytime function?
ARi
CC BY-SA 3.0
2015-12-11T07:56:33.127Z
@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.
Marzio De Biasi
CC BY-SA 3.0
2015-12-11T08:42:27.063Z
@MarzioDeBiasi   I see. The function $f$ is carefully constructed by the delayed diagonalization method. Thanks.
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2017-01-13T17:32:43.697Z
@MarzioDeBiasi If $\mathcal L_1,\mathcal L_2\in\mathsf{NP}\cap\mathsf{CoNP}$ then can we say $\mathcal L_1\cap \mathcal L_2\in\mathsf{NP}\cap\mathsf{coNP}$ as well?
Turbo
CC BY-SA 4.0
2019-05-21T08:08:32.203Z
@MarzioDeBiasi can intersection of a P language and NP complete language be NP complete?
Turbo
CC BY-SA 4.0
2019-05-21T09:44:20.880Z
@Brout: yes, for example: $L_1 \in NPC, L_2 = \Sigma^*$
Marzio De Biasi
CC BY-SA 4.0
2019-05-21T09:46:30.980Z
@MarzioDeBiasi Sorry I meant coNP or coNP complete but not in P.
Turbo
CC BY-SA 3.0
2015-12-10T10:43:32.570Z
2015-12-30T22:01:31.897Z
2015-12-30T22:01:31.897Z
Marzio De Biasi
<p>Can intersection of two languages in NP which are not NP complete be NP complete?</p>

<p>Can intersection of two languages in coNP which are not coNP complete be coNP complete?</p>

<p>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?</p>

CC BY-SA 3.0
2015-12-10T05:27:27.800Z
Very interesting.  :)
Michael Wehar
CC BY-SA 3.0
2015-12-10T09:54:38.637Z
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^*$.
Gamow
CC BY-SA 3.0
2015-12-10T10:29:11.110Z
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.
ARi
<complexity-classes><np>
Intersection of languages in NP
Turbo
# Intersection of languages in NP

(Asked by: username_0 on 2015-12-10)

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?

**Tags:** complexity-classes, np

> **Comments:**
> **username_1**: Very interesting.  :)  
> **username_2**: 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^*$.  
> **username_3**: 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.  

---

## 1 answers

### Answer by username_4 on 2015-12-10. Score: 20 | Accepted answer

Just an extended comment to better explain username_3'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](http://www.cs.umd.edu/~gasarch/COURSES/652/S14/uniform.pdf).

By construction $A\_1, A\_2$ are not NPC, but $A\_1 \cap A\_2 = SAT$

> **Comments:**
> **username_5**: why are $A_1$ and $A_2$ not NPC?  
> **username_4**: @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 username_2 in the comment above.  
> **username_3**: Cant f be jsust about any polytime function?  
> **username_4**: @username_3: 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.  
> **username_5**: @MarzioDeBiasi   I see. The function $f$ is carefully constructed by the delayed diagonalization method. Thanks.  
> **username_0**: @MarzioDeBiasi If $\mathcal L_1,\mathcal L_2\in\mathsf{NP}\cap\mathsf{CoNP}$ then can we say $\mathcal L_1\cap \mathcal L_2\in\mathsf{NP}\cap\mathsf{coNP}$ as well?  
> **username_0**: @MarzioDeBiasi can intersection of a P language and NP complete language be NP complete?  
> **username_4**: @Brout: yes, for example: $L_1 \in NPC, L_2 = \Sigma^*$  
> **username_0**: @MarzioDeBiasi Sorry I meant coNP or coNP complete but not in P.  

---

