0
$\begingroup$

Let $A$ and $B$ be NP-hard problems. For all tuples $(A, B)$ does there exist a polynomial time reduction from $A$ to $B$ and from $B$ to $A$?

Context: I want to prove some problem is NP-hard. Can I pick any problem in NP-hard to reduce from?

$\endgroup$
0
$\begingroup$

A decision problem $L$ is NP-hard when for every problem $H$ in NP, there is a polynomial-time reduction from $H$ to $L$. This is important because it does not necessarily go the other way, you can not say there is a polynomial time reduction from $L$ to $H$. This is because a problem can be NP-Hard and not be in NP. If $A$ and $B$ in your question are both not in NP then there may not be a reduction.

$\endgroup$
  • $\begingroup$ I think I can see an intuitive reason why my statement is not true. If what I asked were true, then it would imply all NP-hard problems are of equal hardness. $\endgroup$ – Daniel May 1 '17 at 18:41
  • $\begingroup$ Yes, and when you consider that the halting problem is NP-Hard, then that does not really work. $\endgroup$ – lPlant May 1 '17 at 18:46
  • $\begingroup$ Further question, can I use any NP-complete problem to prove L is NP-hard? ~~ Edit: Nevermind! A NP-complete problem is in NP, so there must exist a polynomial time reduction. $\endgroup$ – Daniel May 1 '17 at 19:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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