Nazwijmy funkcję wielobiegunową, jeśli dla każdego c> 0 . c > 0
Oczywiste jest, że dla każdego języka utrzymuje, że dla każdego superminomalnego ograniczenia czasowego . Zastanawiam się, czy odwrotność tego stwierdzenia jest również prawdą? To znaczy, jeśli znamy dla każdego superminomialnego ograniczenia czasowego , czy oznacza to ? Innymi słowy, czy prawdą jest, że
gdzie przecięcie jest przejmowane przez każdą superminomię .
cc.complexity-theory
ds.algorithms
complexity-classes
Andras Farago
źródło
źródło
Odpowiedzi:
Tak.
W rzeczywistości, przez McCreight-Meyer Unii twierdzenia (twierdzenie 5.5 McCreight i Meyer, 1969 , darmowa wersja tutaj )f P=DTIME(f(n))
to wynik, który moim zdaniem jest spowodowane Manuel Blum, istnieje pojedyncza funkcja taka, że . Ta funkcja jest z konieczności wielobiegunowa, ale „ledwo”.P = D T I M E ( f ( n ) )Twierdzenie to stosuje się bardziej ogólnie do każdej miary złożoności Bluma i każdej klasy unii gdzie jest ce, zbiorem własnym całkowite funkcje obliczalne. (Zestaw funkcji występuje, jeśli istnieje jedna częściowa funkcja obliczeniowa taka, że gdzie . Ograniczenie własne oznacza, że dla każdego skończonego podzbioru istnieje funkcja w która dominuje nad wszystkimi prawie wszędzie. "Φ ⋃f∈SBLUMΦ(f(n)) S S F(i,x⃗ ) S={fi(x⃗ )|i∈N} faja(x⃗ ) :=F( ja ,x⃗ ) S.0⊂ S. S. B L U M Φsol∈ S.0 B L U MΦ "to notacja, której wcześniej nie widziałem, ale mi się podoba :) - używam jej do analogu związanego z klasą złożoności ograniczoną czasowo.)Φ
źródło