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.

  • $\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

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.

  • $\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

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.