# Polynomial-Time Solvability Through NP-Completeness Reductions

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?

• 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. Commented Mar 31 at 15:54
• 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. Commented Mar 31 at 22:39
• 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. Commented May 1 at 17:08

## 1 Answer

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.