Algoritmos de redutibilidade e subexponencial do SERF

Eu tenho uma pergunta sobre a redutibilidade do SERF de Impagliazzo, Paturi e Zane e algoritmos subexponenciais. A definição de redutibilidade do SERF fornece o seguinte:

Se é SERP-redutível a P 2 e ali ó ( 2 ε n ) algoritmo para P 2 para cada ε > 0 , então não é O ( 2 ε n ) algoritmo para P 1 para cada ε > 0 . (O parâmetro de dureza para ambos os problemas é indicado por n .)$P_1$$P_2$$O(2^{\varepsilon n})$$P_2$$\varepsilon > 0$$O(2^{\varepsilon n})$$P_1$$\varepsilon > 0$$n$

Algumas fontes parecem sugerir que o seguinte também é válido:

Se é SERP-redutível a P 2 e ali ó ( 2 S ( n ) ) algoritmo para uma 2 , então não é O ( 2 S ( n ) ) algoritmo para P 1 .$P_1$$P_2$$O(2^{o(n)})$$A_2$$O(2^{o(n)})$$P_1$

Minha pergunta é: essa afirmação realmente vale e, se existir, existe uma redação da prova em algum lugar?

Como pano de fundo, tenho tentado entender a área em torno da hipótese do tempo exponencial. O IPZ define problemas subexponenciais como aqueles que possuem algoritmo O ( 2 ε n ) para cada ε > 0 , mas aparentemente isso não é suficiente à luz do conhecimento atual para implicar a existência de um algoritmo subexponencial para o problema. A mesma lacuna parece estar presente na redutibilidade do SERF, mas estou parcialmente esperando que algo esteja faltando aqui ...$O(2^{\varepsilon n})$$\varepsilon > 0$

EDIT: Como apontado por Ryan nos comentários, um problema pode ter um algoritmo não uniforme com o funcionamento de tempo para qualquer constante ε > 0 (o algoritmo tem acesso a ε ), mas nenhum uniforme 2 o ( n ) o tempo algoritmo.$O(2^{\epsilon n})$$\epsilon > 0$$\epsilon$$2^{o(n)}$

Como uma redução SERVO é uma família de reduções Turing, um para cada , concluo que eles só podem ser usadas para obter S ( 2 ε n ) algoritmos de tempo a partir de O ( 2 ε n ) ou 2 o ( n ) de tempo algoritmos.$\epsilon>0$$O(2^{\epsilon n})$$O(2^{\epsilon n})$$2^{o(n)}$

O seguinte teorema é provado por Chen et al. [2009] .

Teorema 2.4 . Seja uma função não decrescente e ilimitada e Q seja um problema parametrizado. Então, as seguintes afirmações são equivalentes: (1) Q pode ser resolvido no tempo O ( 2 δ f ( k ) p ( n ) ) para qualquer constante δ > 0 , onde p é um polinômio; (2) Q pode ser resolvido no tempo 2 o ( f ( k ) )$f(k)$$Q$
$Q$$O(2^{\delta f(k)}p(n))$$\delta > 0$$p$
$Q$ , onde q é um polinômio.$2^{o(f(k))} q(n)$$q$

Tomando , obtemos que um problema tem um algoritmo de tempo O ( 2 ϵ n ) para cada ϵ > 0 se e somente se ele tiver um algoritmo de tempo 2 o ( n ) .$f(k)=n$$O(2^{\epsilon n})$$\epsilon>0$$2^{o(n)}$

É mencionado no artigo de Chen et al. que essa equivalência havia sido intuitivamente usada antes, mas estava causando alguma confusão entre os pesquisadores.