Basically, is the following statement true?$A \leq_p B$ $\rightarrow$ $B \leq_p A$
If A is poly-time reducible to B, is B poly-time reducible to A?
complexity theory;reductions;polynomial time
Short answer: No.For one example, take $A$ to be the language $A = \{0, 1\}^*$, i.e. the language that contains every possible string. It is polytime reducible to pretty much anything, for example 3-SAT (the reduction outputs the formula $x\wedge y \wedge z$ on every input). But 3-SAT is definitely not reducible to $A$: there is nothing to map unsatisfiable instances to. Maybe a bit less silly. Take $A$ to be any problem in P. Take $B$ to be a problem complete for exponential time (for example the problem of deciding, given a Turing machine $M$, an input $x$, and a number $k$ written in binary, whether $M$ halts on $x$ within $k$ time steps). Because $B$ is complete for exponential time, $A$ is reducible to $B$. Because a polytime reduction from $B$ to $A$ would imply a polytime algorithm for $B$ and therefore for any exponential time problem, contradicting the time hierarchy theorem, such a polytime reduction does not exist.