Czy redukowalność Karp daje całkowite zamówienie?

Czy innymi słowy, czy mamy to dla każdego języka i , lub ? $A$ $B$ $A \leq_p B$ $B \leq_p A$

reductions complexity

— Mal
źródło

Odpowiedzi:

Daleko stąd. Rzeczywiście, każda policzalna sieć dystrybucyjna jest osadzona jako pod-częściowy porządek , nawet jeśli weźmiemy pod uwagę tylko te stopnie pomiędzy dwoma podanymi stałymi językami ( K. Ambos-Spies, Podsieci wielomianowych stopni czasu , Inform. I Kontrola 65 (1): 63–84, 1985). $\leq_p$

— Joshua Grochow
źródło

$A=\varnothing$ $B=\{0,1\}^*$ $x\in A$ $y\in B$

— Daniil Musatov
źródło

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.

Licensed under cc by-sa 3.0 with attribution required.