# $m/p$-equivalence holds after union with an arbitrary finite language

Problem 1: Let $A,B$ be languages over some alphabet $\Sigma$, if $A \equiv_m B$, then for every finite language $C$, $A \cup C \equiv_m B \cup C$.

Problem 2: Problem 1 but using polynomial time reductions.

Note: $A \equiv_m B$ means $A \leq_m B$ and $B \leq_m A$, same for $\equiv_p$. Every finite language can be decided in polynomial time.

By hypothesis, we have reductions $f$ from $A$ to $B$ and $g$ from $B$ to $A$, the obvious choice for a reduction from $A \cup C$ to $B \cup C$ would be: $$h(w) := \begin{cases} w &\text{ if } w \in C\\ f(w) &\text{ if } w \notin C \end{cases},$$ with this definition it follows that if $w \in A \cup B \Rightarrow h(w) \in B \cup C$, however, if $w \notin A \cup C$ I can't say that $h(w) = f(w)\notin B \cup C$, at most, $f(w) \notin B$.

My idea was to redefine $h$ like this:$$h(w) := \begin{cases} w &\text{if } w \in C\\ f(w) &\text{if } w \notin C \land f(w) \notin C\\ X(w) &\text{if } w \notin C \land f(w) \in C \end{cases},$$ where $X(w)$ must lie in $B \cup C$ when $w \in A \backslash C$, and outside $B \cup C$ when $w \notin A \cup C$. The problem now is how to define the mapping $X$, I can't ask whether $w \in A$ or not because $A$ may not be decidable (or decidable in polynomial time for problem 2) and here I'm stuck.

Can't see how to define $X$ without making questions about being in $A$ or $B$, those questions should be avoided because a $TM$ computing $h$ might loop forever. I'm starting to think that the problem needs some hypothesis like $A,B$ being decidable/decidable in polynomial time languages (the problem seems sound to me though, I can't find counterexamples to it).

Hint: You could prove that $A\cup C\equiv_p A$. For both directions, try functions in the form $$h(w)=\left\{\begin{array}{ll}w & w\notin C\\ \textrm{something hardwired} & w\in C.\end{array}\right.$$
• But that'd give the same problem when trying to reduce $A$ to $A \cup C$: if $w \in A \cup C$ then $h(w)$ must be in $A \cup C$, but when $w \in C \backslash A$ $h(w)$ can't be in $A \cup C$. – Gilberto López Oct 26 '17 at 20:45
• @GilbertoLópez That's why you want to hard-wire $h(w)$ for $w\in C\cap A$ and $w\in C\setminus A$: these two parts are both finite. – Willard Zhan Oct 26 '17 at 20:49
• @GilbertoLópez In case you are still wondering how the problem you described on deciding $X(w)$ is solved: You can decide $X(w)$ not by looking at $w$, but by whether $f(w)$ is in $C\cap B$ or $C\setminus B$. – Willard Zhan Oct 26 '17 at 21:03