3
$\begingroup$

Basically, is the following statement true?

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

|cite|improve this question
$\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$

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.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

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.