# Is the difference of two languages in NP-complete an NP-complete too? [closed]

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?

## closed as off-topic by Kaveh, Mohammad Al-Turkistany, Hsien-Chih Chang 張顯之, Jan Johannsen, Lev Reyzin♦Jan 13 '17 at 19:30

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Kaveh, Mohammad Al-Turkistany, Hsien-Chih Chang 張顯之, Jan Johannsen, Lev Reyzin
If this question can be reworded to fit the rules in the help center, please edit the question.

• 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 Jan 2 '17 at 6:51
• This can be an undergraduate homework assignment and is therefore off-topic here. – Lev Reyzin Jan 13 '17 at 19:31

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.