-3
$\begingroup$

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?

$\endgroup$

closed as off-topic by domotorp, Aryeh, Gamow, a3nm, Emil Jeřábek Feb 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.

0
$\begingroup$

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.

$\endgroup$

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