Warum sind alle Probleme in FPTAS auch in FPT?

Laut dem Wikipedia-Artikel über Polynom-Zeit-Approximationsschemata :

Alle Probleme in FPTAS sind mit festen Parametern nachvollziehbar.

Dieses Ergebnis überrascht mich - diese Klassen scheinen sich völlig zu unterscheiden. FPTAS charakterisiert Probleme dadurch, wie einfach sie zu approximieren sind, während FPT Probleme durch ihre Schwierigkeit relativ zu bestimmten Parametern charakterisiert. Leider bietet Wikipedia (zum Zeitpunkt, an dem ich diese Frage stelle) kein Zitat dafür an.

Gibt es einen Standardnachweis für dieses Ergebnis? Oder gibt es eine Quelle, die ich konsultieren könnte, um mehr über diese Verbindung zu erfahren?

Es gibt tatsächlich ein stärkeres Ergebnis; Ein Problem liegt in der Klasse wenn es ein fptas ^{1 hat} : eine ε- Näherung, die in einer durch ( n + 1 begrenzten Zeit begrenzten Zeit läuft)$\mathrm{FPTAS}$$\varepsilon$(dh Polynom sowohl in der Größe als auch im Approximationsfaktor). Es gibt eine allgemeinere KlasseEPTAS,die die anf(1gebundene Zeit) entspannt$(n+\frac{1}{\varepsilon})^{\mathcal{O}(1)}$$\mathrm{EPTAS}$- im wesentlichen eineFPT-ähnliche Laufzeit in Bezug auf den Approximationsfaktor.$f(\frac{1}{\varepsilon})\cdot n^{\mathcal{O}(1)}$$\mathrm{FPT}$

Es ist klar, dass eine Teilmenge von E P T A S ist , und es stellt sich heraus, dass E P T A S eine Teilmenge von F P T im folgenden Sinne ist:$\mathrm{FPTAS}$$\mathrm{EPTAS}$$\mathrm{EPTAS}$$\mathrm{FPT}$

Satz Wenn ein NPO-Problem ein$\Pi$ Eptas hat, dann ist , das durch die Kosten der Lösung parametrisiert wird, mit festen Parametern nachvollziehbar.$\Pi$

Der Satz und der Beweis werden in Flum & Grohe [1] als Satz 1.32 (S. 23-24) gegeben, und sie schreiben ihn Bazgan [2] zu, was ihn zwei Jahre vor Cai & Chens schwächerem Ergebnis (aber in Französisch) wiedergibt technischer Bericht).

Ich werde eine Skizze des Beweises geben, weil ich denke, dass es ein schöner Beweis des Satzes ist. Der Einfachheit halber mache ich die Minimierungsversion, mache mental nur die entsprechenden Inversionen für die Maximierung.

Beweis. Sei die Eptas für Π , dann können wir einen parametrisierten Algorithmus A ' für Π konstruieren, der durch die Lösungskosten k wie folgt parametrisiert wird : Bei gegebener Eingabe ( x , k ) führen wir A für Eingabe x aus, wobei wir ε : = $A$$\Pi$$A'$$\Pi$$k$$(x,k)$$A$$x$ (dh wir wählen das an1+1gebundene Approximationsverhältnis$\varepsilon := \frac{1}{k+1}$ ). Seiydie Lösung,Kosten(x,y)die Kosten vonyundr(x,y)das tatsächliche Näherungsverhältnis vonyzuopt(x), dhKosten(x,y)=r(x,y))⋅opt(x).$1+\frac{1}{k+1}$$y$$\text{cost}(x,y)$$y$$r(x,y)$$y$$\text{opt}(x)$$\text{cost}(x,y) = r(x,y)\cdot \text{opt}(x)$

Wenn , dann übernehmen, wie es deutlich opt ( x ) ≤ Kosten ( x , y ) ≤ k . Wenn die Kosten ( x , y ) > k sind , lehnen Sie als r ( x , y ) ≤ 1 + $\text{cost}(x,y) \leq k$$\text{opt}(x) \leq \text{cost}(x,y) \leq k$$\text{cost}(x,y) > k$ alsAist einEptasund$r(x,y) \leq 1+\frac{1}{k+1}$$A$

$A'$$A$$\Box$

$\mathrm{FPT}$$\mathrm{EPTAS}$$\mathrm{FPT}$

Fußnoten:

1. Ein fptas (äquivalent eptas oder ptas ) ist ein Näherungsschema, bei dem die Laufzeit wie oben beschrieben begrenzt ist. Die Klasse $\mathrm{FPTAS}$ (äquiv. $\mathrm{EPTAS}$, $\mathrm{PTAS}$) ist die Menge der Probleme in $\mathrm{NPO}$ die haben ein solches Schema.

[1]: J. Flum und M. Grohe, Parametrisierte Komplexitätstheorie , Springer, 2006.
[2]: C. Bazgan. Schémas d'approximation et complexité paramétrée , Bericht der DEA, Université Paris Sud, 1995.