# 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.

Given an instance $$x$$ of $$A$$, reduce it to an instance $$y$$ of $$A \cup B$$ as follows:

• Check (in polynomial time) if $$x \in B$$, if the answer is yes, then $$x \not\in A$$ since $$A \cap B = \emptyset$$. Pick any $$y \in \Sigma^* \setminus (A \cup B)$$ (which is non-empty by hypothesis).

• If $$x \not\in B$$, then $$x \in A \cup B \iff x \in A$$. Pick $$y=x$$.