# 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?

• 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.