1
$\begingroup$

Let A and B be NP-complete problems. Suppose I have established reductions from problem A to problem B and vice versa. Now, considering a specific instance (or set of instances) of problem A that can be solved efficiently in polynomial time, does this imply that the instances reduced to problem B can also be solved in polynomial time? In other words, does the polynomial-time solvability of instances of problem A extend to instances of problem B through the established reductions?

$\endgroup$
3
  • $\begingroup$ I would say no, unless the particular reduction is a restriction or isomorphism that preserves the particular property of A which is “easier” to solve. Otherwise, there’s no guarantee that the corresponding subset of B after the reduction can be solved efficiently. It’s possible that what you’re describing is a separate complexity class (I do not know). I’m just kicking off the discussion. $\endgroup$ Mar 31 at 15:54
  • 2
    $\begingroup$ One way to think about this is to define a problem A' that contains those instances of A that have the special structure that makes them efficiently solvable. Let problem B' contain those instances of B that, if given to the reduction from B to A, produce an instance of A'. Then B' is also polynomially solvable: both A' and B' are in P. What exactly B' will look like may or may not be easy to say. $\endgroup$
    – Neal Young
    Mar 31 at 22:39
  • $\begingroup$ Trivially if you can reduce an instance of B to an efficiently solvable instance of A, then that instance of B is efficiently solvable just by using the reduction and the algorithm for A. $\endgroup$
    – rus9384
    May 1 at 17:08

1 Answer 1

0
$\begingroup$

Yes, that would be the case, and here is my argument. Suppose there is a polynomial time reduction problem $A$ to problem $B$. So basically, we have a mapping function $f$ that converts any input of problem $A$ into an input of problem $B$ in polynomial time. Now we are to run a solver that can solve problem $B$, which is typically the bottleneck in cases of NP-hard problems. Now, as you said, some special class of instances of problem $B$ may indeed be solved in polynomial time. Thus, by virtue of the polynomial time mapping function $f$, we clearly have a polynomial time solvable subset (which may also be empty) of instances of problem $A$ that map to those special instances of problem $B$. Also, keep in mind that any reduction is a one-way path; you cannot comment on the other direction using that reduction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.