# Do all NP-hard problems have a reduction from one to another (Either A $\leq_m$ B or B $\leq_m$ A)

Given two problems, $$A$$ and $$B$$, that are NP-hard. Is either one of the following is true?

1. $$A \leq_m$$ B
2. $$B \leq_m$$ A

In other words, is there always a relationship between any two arbitrary NP-hard problems?

Also, I am speaking of polynomial time reductions, but I don't think specifying that will change the answer to this question.

• @PålGD I think the Halting problem is NP-hard, meaning that SAT does reduce to it. But I am asking for any two arbitrary NP-hard problems, not just SAT and the Halting problem. I don't think that SAT reducing to the Halting problem shows that one of the conditions I listed must be true (or if my "conjecture" is false). Forgive me if I misunderstood your comment. Apr 21, 2023 at 19:02

Absolutely not. See you are talking about $$NP-hard$$ problems. $$NP-hard$$ problems are not necessarily in $$NP$$. Thats why they may not be reducible from one another. Cor example $$SAT$$ is $$NP-hard$$ as well as $$HALT$$. $$SAT$$ can be reduced to $$HALT$$ but the opposite is not true cause otherwise you will solve the halting problem.
Edit: I misunderstood the problem. For any two $$NP-hard$$ problems $$A,B$$ itamy not be possible to reduce one to another. For example take $$A$$ as $$NEXP-complete$$ problem and $$B$$ as $$coNEXP-complete$$ problem. Natural believe is $$NEXP\neq coNEXP$$. Hence there should not be any reduction from $$A$$ to $$B$$ or $$B$$ to $$A$$