[Solved]: If A is poly-time reducible to B, is B poly-time reducible to A?

Problem Detail: 

Basically, is the following statement true?

$A \leq_p B$ $\rightarrow$ $B \leq_p A$

Asked By : robowolverine

Answered By : Sasho Nikolov

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11292