2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.