I have proved that $\overline{A}\le\overline{B}$ is true, but I have no idea how to prove or disprove the opposite direction.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ (Is $\lnot B\le \lnot A$ the complement of $B \le A$? (didn't get \overline to show consistently in a comment)) $\endgroup$– greybeardCommented Jan 27 at 10:06
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
The claim is false. There are several ways to show it. Note that if $\overline{B} \leq_m \overline{A}$, then $B\leq_m A$ (this is what you've shown). Hence, if by contradiction the claim is true, then we can write it as $A \leq _m B \to B\leq_m A$, which is clearly wrong. Why? because it simply says "if $B$ is harder than $A$, then $A$ is harder than B". Hence, an immediate classical counter-example would be, an "easy" problem $A\in \text{R}$, and a "hard" problem $B\notin \text{R}$.
Edit: I focused on the intuition that you should have when reading such claims. If you do not see immediately why what I wrote serves as a counter-example, then I suggest to think about it, or you can note that every non-trivial language is $R$-hard.
answered Jan 28 at 10:40
$\begingroup$
$\endgroup$
No. Take $A = \emptyset$ and $B = \{0\}$. A reduction $f$ from $A$ to $B$ is the function $f(x) = \varepsilon$ since $x \not\in A$ (regardless of the choice of $x$) and $\varepsilon\not\in B$. However $0 \not\in \overline{B}$ and there is no function $g$ such that $g(0) \not\in \overline{A} = \Sigma^*$, hence there is no reduction from $\overline{B}$ to $\overline{A}$.
