# NP-hard proof by reduction [closed]

I show that problem $$A$$ has a polynomial-time reduction to $$B$$ which is NP-hard, in order to use the algorithm $$AL$$ which is able to give an approximate solution of $$B$$ to solve $$A$$.

Then, I need to show that $$A$$ is NP-hard since I should to prove that $$B$$ has a polynomial-time reduction to $$A$$? Assume that the demonstration steps that $$B$$ has a polynomial reduction at $$A$$ are the inverse of the demonstration steps that $$A$$ has a polynomial reduction at $$B$$. Do I have to do it again in the second proof?

## closed as off-topic by domotorp, Aryeh, Gamow, a3nm, Emil JeřábekFeb 7 at 17:29

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – domotorp, Aryeh, Gamow, a3nm, Emil Jeřábek
If this question can be reworded to fit the rules in the help center, please edit the question.

So, let's get it into parts. First, let's assume that $$A$$ is proved to be Np-hard. We will also assume the existence of the algorithm $$AL$$, which provides an approximative solution to problem $$B$$ (which is also NP-Hard). Then, in order to use AL for providing an approximative solution for $$A$$, all you need is to show a polynomial-time reduction from $$B$$ to $$A$$.
For the second case, we will assume that you still need to prove that $$A$$ is NP-Hard. Then, you need to show a polynomial-time reduction from $$B$$ to $$A$$ and them another polynomial-time reduction from $$A$$ to $$B$$. In addition, you will also need to show that $$A$$ is in $$NP$$.