Disjoint union of NP-hard problem and P problem is NP-hard

Let $Σ = \{0, 1\}$ and let $A, B ⊆ Σ^*$ be languages. Prove that if $A$ is NP-hard, $B$ is in P,
$A ∩ B = ∅$, and $A ∪ B ≠ Σ^*$, then $A ∪ B$ in NP-hard.

How can I go about proving $A ∪ B$ is NP-hard given the conditions? Any help would be appreciated.

Let $L$ be any language in NP. Since $A$ is NP-hard, there is a polytime reduction $f$ such that $x \in L$ iff $f(x) \in A$. We want to convert $f$ to a polytime reduction $g$ such that $x \in L$ iff $g(x) \in A \cup B$.

What prevents $f$ from working? Let's consider three cases:

• $f(x) \in A$. In this case, $f(x) \in A \cup B$ as well.

• $f(x) \notin A$, and also $f(x) \notin B$. In this case, $f(x) \notin A \cup B$ as well.

• $f(x) \notin A$, but $f(x) \in B$. In this case, $f(x) \in A \cup B$. This is the problematic case.

The difficult case is $f(x) \in B$. Fortunately, since $B$ is in P, we can test whether this case happens. When it does, we would like to output something which is not in $A \cup B$. Here it is helpful (and necessary!) that $A \cup B \neq \Sigma^*$. Indeed, we can pick some arbitrary $z \notin A \cup B$, and choose this as our output when $f(x) \in B$.

Here is what the updated reduction looks like:
$$
g(x) =
\begin{cases}
z & \text{if } f(x) \in B, \\
f(x) & \text{otherwise}.
\end{cases}
$$
Does this work? Let us prove that it does.

If $f(x) \in B$, then since $A$ and $B$ are disjoint, we are guaranteed that $f(x) \notin A$, and so $x \notin L$. In this case $g(x) = z \notin A \cup B$, as needed.

If $f(x) \notin B$ then $g(x) = f(x)$, and moreover $g(x) = f(x) \in A \cup B$ iff $f(x) \in A$ iff $x \in L$, again as needed.

Finally, note that $g$ can be implemented in polynomial time, since $f$ can be so implemented, and $B$ is in P.

StackExchange Computer Science Q#125332, answer score: 4