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?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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.