4
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ @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. $\endgroup$ Apr 21, 2023 at 19:02

2 Answers 2

2
$\begingroup$

No, the polytime m-degrees are not linearly ordered even above SAT.

We can get even stronger incomparability: there are sets which aren't even arbitrary-time Turing-comparable. This was proved by Kleene and Post (Friedberg and Muchnik proved an elaboration where the sets involved are also required to be c.e.).

$\endgroup$
1
$\begingroup$

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$

$\endgroup$
1
  • $\begingroup$ Hello. This is not what I am asking. I am asking if there exists a reduction from A to B (SAT to HALT) or B to A (HALT to SAT). For any two problems. Because SAT reduces to HALT, this holds true. I think your question answers if both of these conditions are true, not either. $\endgroup$ Apr 22, 2023 at 17:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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