Pourquoi tous les problèmes dans FPTAS sont-ils également dans FPT?

Selon l'article de Wikipedia sur les schémas d'approximation du temps polynomial :

Tous les problèmes dans FPTAS sont traitables à paramètres fixes.

Ce résultat me surprend - ces classes semblent être totalement différentes les unes des autres. FPTAS caractérise les problèmes par leur facilité d'approximation, tandis que FPT caractérise les problèmes par leur difficulté par rapport à certains paramètres. Malheureusement, Wikipedia (au moment où je pose cette question) ne fournit aucune citation à ce sujet.

Existe-t-il une preuve standard de ce résultat? Ou existe-t-il une source que je pourrais consulter pour en savoir plus sur cette connexion?

Il y a en fait un résultat plus fort; Un problème est dans la classe s'il a un fptas ¹ : une -approximation fonctionnant dans le temps délimité par (c'est-à-dire polynôme dans la taille et le facteur d'approximation). Il existe une classe plus générale qui détend le temps lié à - essentiellement un -comme le temps d'exécution par rapport au facteur d'approximation. ε ( n + $\mathrm{FPTAS}$$\varepsilon$EPTASf($(n+\frac{1}{\varepsilon})^{\mathcal{O}(1)}$$\mathrm{EPTAS}$FP$f(\frac{1}{\varepsilon})\cdot n^{\mathcal{O}(1)}$$\mathrm{FPT}$

Il est clair que est un sous-ensemble de , et il s'avère que est un sous-ensemble de dans le sens suivant:E P T A S E P T A S F P $\mathrm{FPTAS}$$\mathrm{EPTAS}$$\mathrm{EPTAS}$$\mathrm{FPT}$

Théorème Si un problème NPO a un$\Pi$Π eptas, alors paramétré par le coût de la solution est traitable à paramètre fixe.$\Pi$

Le théorème et la preuve sont donnés dans Flum & Grohe [1] comme Théorème 1.32 (pp. 23-24), et ils l'attribuent à Bazgan [2], ce qui le met deux ans avant le résultat plus faible de Cai & Chen (mais en français) rapport technique).

Je vais donner un croquis de la preuve, car je pense que c'est une belle preuve du théorème. Pour plus de simplicité, je ferai la version de minimisation, je ferai juste mentalement les inversions appropriées pour la maximisation.

Preuve. Soit les eptas pour , alors nous pouvons construire un algorithme paramétré pour paramétré par le coût de la solution comme suit: étant donné l'entrée , nous exécutons sur l'entrée où nous mettons (c'est-à-dire que nous choisissons le rapport d'approximation lié ). Soit la solution, le coût de et le rapport d'approximation réel de àΠ A ′ Π k ( x , k ) A x ε : = $A$$\Pi$$A'$$\Pi$$k$$(x,k)$$A$$x$ 1+$\varepsilon := \frac{1}{k+1}$ ycoût(x,y)yr(x,y)yopt(x)coût(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)$ , c'est-à-dire .$\text{cost}(x,y) = r(x,y)\cdot \text{opt}(x)$

Si , alors acceptez, comme clairement . Si , rejetez comme car est un eptas etopt ( x ) ≤ coût ( x , y ) ≤ k coût ( x , y ) > k 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$$r(x,y) \leq 1+\frac{1}{k+1}$$A$

Bien sûr, vous obtenez le temps de fonctionnement lié à simplement parce que est un eptas . $A'$$A$$\Box$

Bien sûr, comme le souligne Pål, les résultats de dureté paramétrés impliquent la non-existence de tout eptas, sauf en cas d'effondrement, mais il y a des problèmes dans sans eptas (ou même ptas ), donc est un sous-ensemble strict de (au sens du théorème).$\mathrm{FPT}$$\mathrm{EPTAS}$$\mathrm{FPT}$

Notes de bas de page:

1. Un fptas (de manière équivalente des eptas ou ptas ) est un schéma d'approximation avec le temps d'exécution limité comme décrit ci-dessus. La classe (équiv. , ) est l'ensemble des problèmes dans qui ont un tel schéma.$\mathrm{FPTAS}$$\mathrm{EPTAS}$$\mathrm{PTAS}$$\mathrm{NPO}$

[1]: J. Flum et M. Grohe, Parameterized Complexity Theory , Springer, 2006.
[2]: C. Bazgan. Schémas d'approximation et complexité paramétrée , Rapport de DEA, Université Paris Sud, 1995.