Basically, is the following statement true?
$A \leq_p B$ $\rightarrow$ $B \leq_p A$
3
$\begingroup$
$\endgroup$
-
1$\begingroup$ Restricting $A$, $B$ to $NP$, seems like you are basically asking whether $P = NP$. $\endgroup$ – Aryabhata Apr 13 '13 at 22:21
-
3$\begingroup$ No. Intuitively, $A$ reducible to $B$ means that all of $A$ can be translated into a part of $B$. If $B$ is solvable, the part to which $A$ maps is solvable, and so is $A$. But outside the piece of $B$ to which $A$ maps there might be instances that are much harder than any of $A$. $\endgroup$ – vonbrand Apr 13 '13 at 23:09
-
$\begingroup$ @vonbrand Thanks! This is the simplest answer I could hope for! The answer makes a lot of sense when put this way. $\endgroup$ – robowolverine Apr 13 '13 at 23:55
7
$\begingroup$
$\endgroup$
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.
1
$\begingroup$
$\endgroup$
If $A,B$ are NP-complete, then every problem in $NP$ is polytime reducible to $A$ and polytime reducible to $B$. In particular $A$ is polytime reducible to $B$ and vice-versa. So this answers the question for NP-complete problems.
