A is an NP-Complete language, B is a language in P, prove that A∪B is NP-Complete

Question

This is the data given in the question:

• A is an NP-Complete language
• B is a language in P
• B ⊆ $A^\complement$
• $B\ne A^\complement$

Prove that $A\cup$B is NP-Complete.

This is what i tried so far:

This is the venn diagram of the problem as i see it.

Now We already know that $A\cup B$ is NP since both A and B are in NP and NP is closed under union. So we can find a reduction from A to $A\cup B$.

But i could not find any reduction that can satisfy this.

Answer 1

You are right, it follows directly that $A \cup B$ is in NP. For a reduction, why not simply reduce $A$?

Decide membership of $A$ as follows:

1. Decide membership of $A \cup B$.
2. Decide membership of $B$.

We only need that $A$ and $B$ are disjoint and that $B$ is in $P$, we don't even need the last property (it follows from the others assuming $P \neq NP$).