Algorytmy redukcji SERF i algorytmy podwykładnicze

Mam pytanie dotyczące redukowalności SERF impagliazzo, Paturi i Zane'a oraz algorytmów podwykładniczych. Definicja SERF-redukowalności daje następujące:

Jeśli jest redukowalne przez SERF do P 2 i istnieje algorytm O ( 2 ε n ) dla P 2 dla każdego ε > 0 , wówczas istnieje algorytm O ( 2 ε n ) dla P 1 dla każdego ε > 0 . (Parametr twardości dla obu problemów jest oznaczony przez n .)$P_1$$P_2$$O(2^{\varepsilon n})$$P_2$$\varepsilon > 0$$O(2^{\varepsilon n})$$P_1$$\varepsilon > 0$$n$

Niektóre źródła zdają się sugerować, że następujące:

Jeżeli jest SERF-zredukować do P 2 i tam O ( 2 O ( n ) ) algorytm A 2 , to jest O ( 2 O ( n ) ) algorytm P 1 .$P_1$$P_2$$O(2^{o(n)})$$A_2$$O(2^{o(n)})$$P_1$

Moje pytanie brzmi: czy to ostatnie twierdzenie rzeczywiście się utrzymuje, a jeśli tak, to czy jest gdzieś spisanie dowodu?

W tle starałem się zrozumieć obszar wokół hipotezy o wykładniczym czasie. IPZ definiuje problemy podwykładnicze jako te, które mają algorytm dla każdego ε > 0 , ale najwyraźniej nie jest to wystarczające w świetle obecnej wiedzy, by sugerować istnienie algorytmu podwykładniczego dla problemu. Ta sama luka wydaje się być obecna w redukowalności SERF, ale częściowo spodziewam się, że coś mi tu brakuje ...$O(2^{\varepsilon n})$$\varepsilon > 0$

$O(2^{\epsilon n})$$\epsilon > 0$$\epsilon$$2^{o(n)}$

$\epsilon>0$$O(2^{\epsilon n})$$O(2^{\epsilon n})$$2^{o(n)}$

Poniższe twierdzenie zostało udowodnione przez Chen i in. [2009] .

$f(k)$$Q$
$Q$$O(2^{\delta f(k)}p(n))$$\delta > 0$$p$
$Q$$2^{o(f(k))} q(n)$$q$

$f(k)=n$$O(2^{\epsilon n})$$\epsilon>0$$2^{o(n)}$

Jest wspomniany w pracy Chen i in. że ta równoważność była wcześniej stosowana intuicyjnie, ale powodowała pewne zamieszanie wśród badaczy.