La réductibilité de Karp donne-t-elle une commande totale?

Ou avec d'autres mots, avons-nous cela pour chaque langue et , ou ?$A$$B$$A \leq_p B$$B \leq_p A$

Loin de là. En effet, tout réseau distributif dénombrable s'incorpore comme un ordre sous-partiel de , même si nous ne considérons que ces degrés entre deux langues fixes données ( K.Ambos-Spies, Sous-réseaux des degrés de temps polynomiaux , Inform. & Control 65 (1): 63-84, 1985).$\leq_p$

Comme contre-exemple trivial, on peut considérer et B = { 0 , 1 } ∗ . Aucun des deux n'est réductible à l'autre, car x ∈ A est toujours faux et y ∈ B est toujours vrai.$A=\varnothing$$B=\{0,1\}^*$$x\in A$$y\in B$