Ergibt die Karp-Reduzierbarkeit eine Gesamtbestellung?

Oder mit anderen Worten, haben wir das für jede Sprache und , oder ?$A$A ≤ p B B ≤ p$B$$A \leq_p B$$B \leq_p A$

Weit davon entfernt. In der Tat wird jedes zählbare Verteilungsgitter als eine Ordnung von , selbst wenn wir nur diese Grade zwischen zwei gegebenen festen Sprachen betrachten ( K. Ambos-Spies, Untergitter der Polynomzeitgrade , Inform. & Control 65 (1): 63 & ndash; 84, 1985).$\leq_p$

Als Gegenbeispiel trivial, kann man überlegen , und B = { 0 , 1 } * . Keines ist auf das andere reduzierbar, da x ∈ A immer falsch ist und y ∈ B immer wahr ist.$A=\varnothing$$B=\{0,1\}^*$$x\in A$$y\in B$