Basically, is the following statement true?
$A \leq_p B$ $\rightarrow$ $B \leq_p A$
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityBasically, is the following statement true?
$A \leq_p B$ $\rightarrow$ $B \leq_p A$
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.
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.