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

Question

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.

Answer 1

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.

Answer 2

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