NP-Complete Proofs Reductions (Direction)?

Question

Why do you have to reduce an NP-Complete algorithm to the algorithm you're trying to prove is NP-complete, and not vice versa? I feel like the explanation is simple-and i have searched it online, without success-but my mind isn't wrapping around it very well.

Thank you!:)

Answer 1

Because if you can reduce problem A to problem B, then problem B cannot be any easier than A. After all, you now have a new way to solve instances of problem A: turn it into an instance of problem B and solve that. If B is easy, then A is also easy by that process.

That only works if the process of translating the problem instance is itself not hard, which is why you also have to show that. If the translation was allowed to be hard, it could just solve the problem and let B be trivial.

And by itself that only proves problem B NP-hard, in order to show that problem B is NP-complete you also have to prove it's in NP (which is usually easier than the reduction).

The other way around just shows that your problem is no harder than NP-complete, which is not entirely useless, but generally less interesting. For example you can solve the problem "is there an integer x such that x*3=9" with a SAT solver using a circuit for binary multiplication and encoding that as a SAT instance, but that problem is much easier.