patternMinor
$m/p$-equivalence holds after union with an arbitrary finite language
Viewed 0 times
afterfinitewitharbitraryunionlanguageholdsequivalence
Problem
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).
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).
Solution
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.$$
$$h(w)=\left\{\begin{array}{ll}w & w\notin C\\ \textrm{something hardwired} & w\in C.\end{array}\right.$$
Context
StackExchange Computer Science Q#83019, answer score: 2
Revisions (0)
No revisions yet.