patternMinor
Do all NP-hard problems have a reduction from one to another (Either A $\leq_m$ B or B $\leq_m$ A)
Viewed 0 times
fromallleq_mhardeitheronereductionanotherproblemshave
Problem
Given two problems, $A$ and $B$, that are NP-hard. Is either one of the following is true?
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.
- $A \leq_m$ B
- $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.
Solution
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.).
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.).
Context
StackExchange Computer Science Q#159745, answer score: 2
Revisions (0)
No revisions yet.