NP-hard proof by reduction [closed]

Question

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?

Answer 1

Your description is somewhat confusing.

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$.

It's simpler than what you are trying to do.