Or with other words, do we have that for every language $A$ and $B$, $A \leq_p B$ or $B \leq_p A$?
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:
Sign up
Sign up
Here's how it works:
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
|
|
|
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). |
|||
|
|
