SERF-Reduzierbarkeit und subexponentielle Algorithmen

Ich habe eine Frage zur SERF-Reduzierbarkeit von Impagliazzo, Paturi und Zane und zu subexponentiellen Algorithmen. Die Definition der SERF-Reduzierbarkeit ergibt folgendes:

Ist SERF-reduzierbar auf P 2 und gibt es einen O ( 2 ε n ) -Algorithmus für P 2 für jedes ε > 0 , dann gibt es einen O ( 2 ε n ) -Algorithmus für P 1 für jedes ε > 0 . (Der Härteparameter für beide Probleme ist mit n bezeichnet .)$P_1$$P_2$$O(2^{\varepsilon n})$$P_2$$\varepsilon > 0$$O(2^{\varepsilon n})$$P_1$$\varepsilon > 0$$n$

Einige Quellen scheinen zu implizieren, dass das Folgende auch gilt:

Ist SERF-reduzierbar auf P 2 und gibt es einen O ( 2 o ( n ) ) - Algorithmus für A 2 , dann gibt es einen O ( 2 o ( n ) ) - Algorithmus für P 1 .$P_1$$P_2$$O(2^{o(n)})$$A_2$$O(2^{o(n)})$$P_1$

Meine Frage ist, ob diese letztere Behauptung tatsächlich zutrifft, und wenn ja, gibt es irgendwo eine Zusammenfassung des Beweises?

Als Hintergrund habe ich versucht, den Bereich um die Exponentialzeithypothese zu verstehen. IPZ definieren subexponentielle Probleme als solche, die einen -Algorithmus für jedes ε > 0 haben , aber dies ist anscheinend im Lichte des gegenwärtigen Wissens nicht ausreichend, um die Existenz eines subexponentiellen Algorithmus für das Problem zu implizieren. Dieselbe Lücke scheint in der SERF-Reduzierbarkeit vorhanden zu sein, aber ich erwarte teilweise, dass mir hier etwas fehlt ...$O(2^{\varepsilon n})$$\varepsilon > 0$

BEARBEITEN: Wie Ryan in den Kommentaren ausgeführt hat, kann ein Problem einen ungleichmäßigen Algorithmus mit der Laufzeit für jede Konstante ϵ > 0 (der Algorithmus hat Zugriff auf ϵ ) haben, aber keine einheitliche 2 o ( n ) -Zeit Algorithmus.$O(2^{\epsilon n})$$\epsilon > 0$$\epsilon$$2^{o(n)}$

Als SERF Reduktion eine Familie von Turing Reduzierungen ist, eine für jedes , schließe ich , dass sie nur verwendet werden können , erhalten O ( 2 ε n ) Zeitalgorithmen von O ( 2 ε n ) oder 2 o ( n ) Zeit Algorithmen.$\epsilon>0$$O(2^{\epsilon n})$$O(2^{\epsilon n})$$2^{o(n)}$

Der folgende Satz wird von Chen et al. [2009] .

Satz 2.4 . Sei eine nicht abnehmende und unbegrenzte Funktion und sei Q ein parametrisiertes Problem. Dann sind die folgenden Aussagen äquivalent: (1) Q kann in der Zeit O ( 2 δ f ( k ) p ( n ) ) für jede Konstante δ > 0 gelöst werden , wobei p ein Polynom ist; (2) Q kann in der Zeit 2 o ( f ( k ) ) q gelöst werden$f(k)$$Q$
$Q$$O(2^{\delta f(k)}p(n))$$\delta > 0$$p$
$Q$ , wobei q ein Polynom ist.$2^{o(f(k))} q(n)$$q$

Unter erhalten wir , dass ein Problem , eine hat O ( 2 ε n ) für jeden Algorithmus ε > 0 , wenn und nur wenn es einen hat 2 o ( n ) Algorithmus.$f(k)=n$$O(2^{\epsilon n})$$\epsilon>0$$2^{o(n)}$

Es wird in der Veröffentlichung von Chen et al. dass diese Äquivalenz zuvor intuitiv verwendet worden war, aber dass sie bei Forschern einige Verwirrung stiftete.