If a language $A$ is reducible to some language $B$, does it follow that $B$ is reducible to $A$?
My guess is no, it having something to do with the function $f$ in the definition of $A$ reducing to $B$ needing to be invertible.
1
$\begingroup$
$\endgroup$
-
$\begingroup$ What have you tried? Where did you get stuck? We want to help you with your specific problems, not just do your (home-)work. However, as it is we don't know what this problem is and thus how to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael♦ May 6 '14 at 23:00
5
$\begingroup$
$\endgroup$
This is provably not the case. Let $A$ be any non-trivial language in P (different from $\emptyset$ and $\Sigma^*$), and let $B$ be any EXPTIME-hard language. Clearly $A$ is polytime-reducible to $B$ (since $A$ is polytime and $B$ is non-trivial; or since P$\subseteq$EXPTIME and $B$ is EXPTIME-hard), but if $B$ were polytime-reducible to $A$ then it would follow that EXPTIME=P, contradicting the time hierarchy theorem.
answered May 7 '14 at 0:48
-
$\begingroup$ I see. So it boils down to a "subset but not equal"/"rectangle not square"/"injective not bijective" sort of thing. Thanks for giving an example. $\endgroup$ – AmadeusDrZaius May 7 '14 at 1:39
