Por que todos os problemas no FPTAS também estão no FPT?

De acordo com o artigo da Wikipedia sobre esquemas de aproximação de tempo polinomial :

Todos os problemas no FPTAS são tratáveis com parâmetros fixos.

Esse resultado me surpreende - essas classes parecem ser totalmente diferentes umas das outras. O FPTAS caracteriza problemas pela facilidade com que são aproximados, enquanto o FPTAS caracteriza problemas pela dificuldade em relação a algum parâmetro. Infelizmente, a Wikipedia (no momento em que estou fazendo essa pergunta) não fornece uma citação para isso.

Existe uma prova padrão desse resultado? Ou existe uma fonte que eu poderia consultar para saber mais sobre essa conexão?

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

Este é um teorema de Cai e Chen (JCSS97), afirmando que " se um problema de otimização NP tem um esquema de aproximação totalmente polinomial, então é fixo-parâmetro tratável. " Veja o papel No Fixed-Parâmetro rastreabilidade e Approximability de NP Otimização Problemas .

Gål GD 08/08

E, é claro, como corolário, você obtém " Os problemas de otimização de NP que são sob a redução uniforme não têm um esquema de aproximação de tempo totalmente polinomial, a menos que $W[1]$ $W[1] = FPT$ ".

Gål GD 08/08

@ PålGD- Embora pareça que a escolha da parametrização seja um pouco arbitrária; eles escolhem o parâmetro para ser o valor da solução ideal para a entrada do problema. Suponho que tecnicamente funcione, embora intelectualmente não seja muito gratificante.

templatetypedef

Luke Mathieson deu uma resposta muito boa abaixo, e acho que basta para responder sua pergunta.

Gål GD

Respostas:

Na verdade, há um resultado mais forte; Um problema está na classe se tiver um fptas ¹ : uma aproximação no tempo limitado por $\mathrm{FPTAS}$ $\varepsilon$ (isto é, polinômio tanto no tamanho quanto no fator de aproximação). Existe uma classe mais geralque relaxa o tempo vinculado a $(n+\frac{1}{\varepsilon})^{\mathcal{O}(1)}$ $\mathrm{EPTAS}$ - essencialmente um-like tempo de execução com respeito ao factor de aproximação. $f(\frac{1}{\varepsilon})\cdot n^{\mathcal{O}(1)}$ $\mathrm{FPT}$

Claramente, é um subconjunto de , e verifica-se que é um subconjunto de no seguinte sentido: $\mathrm{FPTAS}$ $\mathrm{EPTAS}$ $\mathrm{EPTAS}$ $\mathrm{FPT}$

Teorema Se um problema NPO tem um $\Pi$ eptas, em seguida, parametrizado pelo custo da solução é fixa parâmetros tratável. $\Pi$

O teorema e a prova são dados em Flum & Grohe [1] como Teorema 1.32 (pp. 23-24), e eles o atribuem a Bazgan [2], o que o coloca dois anos antes do resultado mais fraco de Cai & Chen (mas em francês). relatório técnico).

Vou fazer um esboço da prova, porque acho que é uma boa prova do teorema. Para simplificar, farei a versão de minimização, apenas mentalmente faça as inversões apropriadas para maximização.

$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 de rodapé:

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

[1]: J. Flum e M. Grohe, teoria da complexidade parametrizada , Springer, 2006.
[2]: C. Bazgan. Schémas de aproximação e complexidade paramétrica , Rapport de DEA, Université Paris Sud, 1995.

Luke Mathieson
fonte