Does Karp reducibility yield a total order?

Question

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

Answer 1

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, Inform. & Control 65(1):63-84, 1985).

Answer 2

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.