SERF-reducibilidad y algoritmos subexponenciales

Tengo una pregunta sobre la reducibilidad SERF de Impagliazzo, Paturi y Zane y los algoritmos subexponenciales. La definición de SERF-reducibilidad ofrece lo siguiente:

Si $P_1$ es SERF-reducible a y hay un algoritmo para para cada , entonces hay un algoritmo para para cada . (El parámetro de dureza para ambos problemas se denota por .) O ( 2 ε n ) P 2 ε > 0 O ( 2 ε n ) P 1 ε > 0 $P_2$$O(2^{\varepsilon n})$$P_2$$\varepsilon > 0$$O(2^{\varepsilon n})$$P_1$$\varepsilon > 0$$n$

Algunas fuentes parecen implicar que lo siguiente también es válido:

Si es SERF-reducible a y hay un algoritmo para , entonces hay un algoritmo para .P 2 O ( 2 o ( n ) ) A 2 O ( 2 o ( n ) ) P $P_1$$P_2$$O(2^{o(n)})$$A_2$$O(2^{o(n)})$$P_1$

Mi pregunta es, ¿esta última afirmación realmente se cumple y, si es así, hay algún resumen de la prueba en alguna parte?

Como antecedentes, he estado tratando de entender el área alrededor de la Hipótesis del tiempo exponencial. IPZ define problemas subexponenciales como aquellos que tienen un algoritmo para cada , pero esto aparentemente no es suficiente a la luz del conocimiento actual para implicar la existencia de un algoritmo subexponencial para el problema . La misma brecha parece estar presente en la reducibilidad de SERF, pero en parte espero que me falte algo aquí ...ε > $O(2^{\varepsilon n})$$\varepsilon > 0$

EDIT: Como se ha señalado por Ryan en los comentarios, un problema puede tener un algoritmo no uniforme con el funcionamiento de tiempo para cualquier constante ε > 0 (el algoritmo tiene acceso a ε ), pero no uniforme 2 O ( n ) tiempo algoritmo.$O(2^{\epsilon n})$$\epsilon > 0$$\epsilon$$2^{o(n)}$

Como una reducción SIERVO es una familia de reducciones de Turing, uno para cada , llego a la conclusión de que sólo pueden ser utilizados para obtener O ( 2 ε n ) algoritmos de tiempo de O ( 2 ε n ) o 2 O ( n ) tiempo algoritmos$\epsilon>0$$O(2^{\epsilon n})$$O(2^{\epsilon n})$$2^{o(n)}$

El siguiente teorema es probado por Chen et al. [2009] .

Teorema 2.4 . Sea una función no decreciente y sin límites, y sea Q un problema parametrizado. Entonces las siguientes afirmaciones son equivalentes: (1) Q puede resolverse en el tiempo O ( 2 δ f ( k ) p ( n ) ) para cualquier constante δ > 0 , donde p es un polinomio; (2) Q puede resolverse en el tiempo 2 o ( f ( k ) )$f(k)$$Q$
$Q$$O(2^{\delta f(k)}p(n))$$\delta > 0$$p$
$Q$ , donde q es un polinomio.$2^{o(f(k))} q(n)$$q$

Tomando obtenemos que un problema tiene un algoritmo de tiempo O ( 2 ϵ n ) por cada ϵ > 0 si y solo si tiene un algoritmo de tiempo 2 o ( n ) .$f(k)=n$$O(2^{\epsilon n})$$\epsilon>0$$2^{o(n)}$

Se menciona en el artículo de Chen et al. que esta equivalencia se había usado intuitivamente antes pero que estaba causando cierta confusión entre los investigadores