-7
$\begingroup$

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?

$\endgroup$

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.

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

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.