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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityIf 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.
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.