¿Por qué todos los problemas en FPTAS también están en FPT?

Según el artículo de Wikipedia sobre esquemas de aproximación de tiempo polinomial :

Todos los problemas en FPTAS son manejables de parámetros fijos.

Este resultado me sorprende: estas clases parecen ser totalmente diferentes entre sí. FPTAS caracteriza los problemas por su facilidad de aproximación, mientras que FPT caracteriza los problemas por su dificultad en relación con algún parámetro. Desafortunadamente, Wikipedia (en el momento en que hago esta pregunta) no proporciona una cita para esto.

¿Existe una prueba estándar de este resultado? ¿O hay una fuente que podría consultar para obtener más información sobre esta conexión?

complexity-theory reference-request approximation parameterized-complexity templatetypedef
fuente

Este es un teorema de Cai y Chen (JCSS97), afirmando que " si un problema de optimización NP tiene un esquema de aproximación totalmente en tiempo polinómico, entonces es tratable parámetro fijo. " Ver el documento de la CES, Parámetro docilidad y Approximability de optimización NP problemas .

Pål GD

Y, por supuesto, como corolario se obtiene " Los problemas de optimización de NP que son -duros bajo la reducción uniforme no tienen un esquema de aproximación de tiempo completamente polinomial a menos que $W[1]$ $W[1] = FPT$ ".

Pål GD

@ PålGD- Aunque parece que la elección de la parametrización es algo arbitraria; Eligen el parámetro como valor de la solución óptima para la entrada del problema. Supongo que técnicamente funciona, aunque intelectualmente no es muy satisfactorio.

templatetypedef

Luke Mathieson dio una muy buena respuesta a continuación, y creo que eso es suficiente para responder a su pregunta.

Pål GD

Respuestas:

En realidad hay un resultado más fuerte; Un problema está en la clase si tiene fptas ¹ : una aproximación ejecuta en el tiempo delimitada por $\mathrm{FPTAS}$ $\varepsilon$ (es decir, polinomio tanto en el tamaño como en el factor de aproximación). Hay una clase más generalque relaja el tiempo limitado a $(n+\frac{1}{\varepsilon})^{\mathcal{O}(1)}$ $\mathrm{EPTAS}$ - esencialmente untiempo de ejecución similar acon respecto al factor de aproximación. $f(\frac{1}{\varepsilon})\cdot n^{\mathcal{O}(1)}$ $\mathrm{FPT}$

Claramente, es un subconjunto de , y resulta que es un subconjunto de en el siguiente sentido: $\mathrm{FPTAS}$ $\mathrm{EPTAS}$ $\mathrm{EPTAS}$ $\mathrm{FPT}$

Teorema Si un problema de NPO tiene un $\Pi$ eptas, entonces parametrizado por el costo de la solución es un parámetro fijo manejable. $\Pi$

El teorema y la prueba se dan en Flum & Grohe [1] como Teorema 1.32 (págs. 23-24), y lo atribuyen a Bazgan [2], que lo coloca dos años antes del resultado más débil de Cai y Chen (pero en francés reporte técnico).

Daré un boceto de la prueba, porque creo que es una buena prueba del teorema. Para simplificar, haré la versión de minimización, solo mentalmente hago las inversiones apropiadas para la maximización.

$A$ $\Pi$ $A'$ $\Pi$ $k$ $(x,k)$ $A$ $x$ $\varepsilon := \frac{1}{k+1}$ $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)$

$\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$

opt (x) = \frac{cost (x, y)}{r (x, y)} \geq \frac{k + 1}{1 + \frac{1}{k + 1}} > k

$\text{opt}(x) = \frac{\text{cost}(x,y)}{r(x,y)} \geq \frac{k+1}{1+\frac{1}{k+1}} > k$

$A'$ $A$ $\Box$

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

Notas al pie:

$\mathrm{FPTAS}$ $\mathrm{EPTAS}$ $\mathrm{PTAS}$ $\mathrm{NPO}$

[1]: J. Flum y M. Grohe, Teoría de la complejidad parametrizada , Springer, 2006.
[2]: C. Bazgan. Schémas d'approximation et complexité paramétrée , Rapport de DEA, Université Paris Sud, 1995.

Luke Mathieson
fuente