3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Gilberto López Oct 26 '17 at 20:45
  • 1
    $\begingroup$ @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. $\endgroup$ – Willard Zhan Oct 26 '17 at 20:49
  • $\begingroup$ @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$. $\endgroup$ – Willard Zhan Oct 26 '17 at 21:03

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.