<p>Not necessarily. For example, consider the case where $L_1$ is the empty language and $L_2$ is any NP-complete language. Then certainly $L_1 \in NP$ and $L_2 = L_1 \cup L_2 \in NP\text{-}complete$, but $L_1$ is not itself NP-complete. </p>

CC BY-SA 3.0
2017-01-02T04:56:27.617Z
2017-01-02T04:56:27.617Z
Mikhail Rudoy
<p>Given two languages $L_{1} \in NP$ and $L_{2} \in \textit{NP-complete}$ such that $L_{1} \cup L_{2} \in \textit{NP-complete}$, Is $L_{1}$ in $\textit{NP-complete}$ too? </p>

CC BY-SA 3.0
2017-01-02T06:51:47.277Z
No (and here's a slightly less trivial example than in the answer): Let $L_1 = \{1x : x \in L'\}$ where $L' \in \mathsf{P}$ (or really just $L'$ any language in NP that isn't NP-complete), and let $L_2 = \{0x : x \in SAT\}$.
Joshua Grochow
CC BY-SA 3.0
2017-01-13T19:31:40.483Z
This can be an undergraduate homework assignment and is therefore off-topic here.
Lev Reyzin
<cc.complexity-theory><complexity-classes><np-complete>
Is the difference of two languages in NP-complete an NP-complete too?
Frank Vega
# Is the difference of two languages in NP-complete an NP-complete too?

(Asked by: username_0 on 2017-01-02)

Given two languages $L\_{1} \in NP$ and $L\_{2} \in \textit{NP-complete}$ such that $L\_{1} \cup L\_{2} \in \textit{NP-complete}$, Is $L\_{1}$ in $\textit{NP-complete}$ too?

**Tags:** cc.complexity-theory, complexity-classes, np-complete

> **Comments:**
> **username_1**: No (and here's a slightly less trivial example than in the answer): Let $L_1 = \{1x : x \in L'\}$ where $L' \in \mathsf{P}$ (or really just $L'$ any language in NP that isn't NP-complete), and let $L_2 = \{0x : x \in SAT\}$.  
> **username_2**: This can be an undergraduate homework assignment and is therefore off-topic here.  

---

## 1 answers

### Answer by username_3 on 2017-01-02. Score: 2 | Accepted answer

Not necessarily. For example, consider the case where $L\_1$ is the empty language and $L\_2$ is any NP-complete language. Then certainly $L\_1 \in NP$ and $L\_2 = L\_1 \cup L\_2 \in NP\text{-}complete$, but $L\_1$ is not itself NP-complete.


---

