3
$\begingroup$

TRUE or FALSE Statement:

Assume that $P \neq NP$. Then, for all languages $L_1$ and $L_2$, if $L_1$ is in P and $L_2$ is in NP but not in P then $L_1 \cup L_2$ is in NP but not in P.

I have a doubt about the point: $L_1 \cup L_2$ is in NP but not in P.

I know P is a subset of NP, then $L_1 \cup L_2$ is in NP (because $P \subseteq NP$), but the sentence "is in NP but not in P" it puzzles me.

$\endgroup$
2
  • $\begingroup$ Sounds like you need to figure out whether $L_1 \cup L_2$ is in P. Regarding that, what are your thoughts? What did you try? Where did you get stuck? What have you tried? Have you tried some examples? We're more likely to be able to help you if you can show us some progress and give us some idea of what is preventing you from answering it yourself; just saying "it puzzles me" doesn't give us much insight about what the barrier is. $\endgroup$ – D.W. Dec 27 '19 at 19:11
  • $\begingroup$ Hint: Take $L_1 = \Sigma^*$. $\endgroup$ – Yuval Filmus Dec 27 '19 at 19:14
1
$\begingroup$

From an Hint (by Yuval Filmus), the statement is FALSE because if $L_1=Σ^∗$ then $L_1 \cup L_2=Σ^∗$. I know $Σ^∗$ is in P (i.e., a TM which accepts all strings), and the statement is FALSE.

$\endgroup$
1
  • $\begingroup$ I think the statement is equivalent to the P versus NP problem actually, see my answer for more details. $\endgroup$ – PMercier Jan 17 '20 at 3:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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