If the union of two languages is NP-complete, is one of them NP-complete?

1.4k Views Asked by At

Question 1) If $A\cup B$ is NP-complete, and $A$ is NP, and $B$ is P, then is $A$ NP-complete?

I don't think so but I am unsure. When I try to reduce $A\cup B$ to $A$, I fail because strings in $B$ cannot be decided by a decider for $A$.

Question 2) On the other hand, given $A$ is NP-complete, and $B$ is P, then is $A\cup B$ NP-complete?

1

There are 1 best solutions below

4
On BEST ANSWER

To test whether a string is in $A \cup B$, first test (in polynomial time) whether it is in $B$. If it isn't, you use the $A$-decider to test whether it is in $A$.

For your second problem: what happens if $B$ accepts everything?