<p>As a trivial counterexample, one may consider $A=\varnothing$ and $B=\{0,1\}^*$. Neither is reducible to the other, since $x\in A$ is always wrong and $y\in B$ is always true.</p>

CC BY-SA 3.0
2017-02-23T17:00:59.137Z
2017-02-23T17:00:59.137Z
Daniil Musatov
<p>Far from it. Indeed, any countable distributive lattice embeds as a sub-partial-order of $\leq_p$, even if we only consider those degrees in between two given fixed languages (<a href="http://dx.doi.org/10.1016/S0019-9958(85)80020-6" rel="noreferrer">K. Ambos-Spies, Sublattices of the polynomial time degrees</a>, Inform. &amp; Control 65(1):63-84, 1985).</p>

CC BY-SA 3.0
2017-02-20T21:00:23.890Z
2017-02-20T21:00:23.890Z
Joshua Grochow
<p>Or with other words, do we have that for every language $A$ and $B$, $A \leq_p B$ or $B \leq_p A$?</p>

<reductions><complexity>
Does Karp reducibility yield a total order?
Mal
# Does Karp reducibility yield a total order?

(Asked by: username_0 on 2017-02-20)

Or with other words, do we have that for every language $A$ and $B$, $A \leq\_p B$ or $B \leq\_p A$?

**Tags:** reductions, complexity

---

## 2 answers

### Answer by username_2 on 2017-02-20. Score: 27 | Accepted answer

Far from it. Indeed, any countable distributive lattice embeds as a sub-partial-order of $\leq\_p$, even if we only consider those degrees in between two given fixed languages ([K. Ambos-Spies, Sublattices of the polynomial time degrees](http://dx.doi.org/10.1016/S0019-9958(85)80020-6), Inform. & Control 65(1):63-84, 1985).


---

### Answer by username_1 on 2017-02-23. Score: 1

As a trivial counterexample, one may consider $A=\varnothing$ and $B=\{0,1\}^\*$. Neither is reducible to the other, since $x\in A$ is always wrong and $y\in B$ is always true.


---

