FPT vs W [P] - Complejidad parametrizada

En complejidad parametrizada, ⊆ W [ 2 ] . Se conjetura que cada una de las contenciones es adecuada.$\mathsf{FPT} \subseteq \mathsf{W}[1]$ $\subseteq \mathsf{W}[2]$ $\subseteq \ldots \subseteq \mathsf{W}[P]$

Si entonces .P = W [ P $\mathsf{FPT}=\mathsf{W}[P]$$\mathsf{P}=\mathsf{W}[P]$

¿Pero se sigue que

• Si entonces ? oF P T = W [ P $\mathsf{FPT}=\mathsf{W}[1]$$\mathsf{FPT}=\mathsf{W}[P]$
• Si (para algunas t) entonces ?F P T = W [ P $\mathsf{W}[t-1]=\mathsf{W}[t]$$\mathsf{FPT}=\mathsf{W}[P]$

Esta pregunta es complicada ya que la respuesta (hasta donde yo sé) sigue siendo "no sé".

Para agregar algo de peso a esto, Flum & Grohe [1] dan como problemas abiertos (p. 164):

• ¿Es estricta la jerarquía bajo el supuesto F P T ≠ W [ P ] ?$\mathrm{W}$$\mathrm{FPT} \neq \mathrm{W[P]}$
• Para , ¿la igualdad W [ t ] = W [ t + 1 ] implica W [ t ] = W [ t + 2 ] ?$t \geq 1$$\mathrm{W}[t] = \mathrm{W}[t + 1]$$\mathrm{W}[t] = \mathrm{W}[t + 2]$

Además, en la monografía reciente de Downey y Fellow [2], la declaración más fuerte (directa) que hacen es (p. 521):

Una hipótesis más sutil es que la jerarquía es adecuada y, en particular, W [ 1 ] ≠ W [ 2 ] .$\mathrm{W}$$\mathrm{W}[1] \neq \mathrm{W}[2]$

No hay una declaración siguiente (o posterior) a lo largo de las líneas "de lo contrario, la jerarquía colapsaría", o similar.$\mathrm{W}$

Esto también está precedido por:

Una hipótesis más débil podría ser que para algunos , F P T ≠ W [ t $t$

$$\mathrm{FPT} \neq \mathrm{W}[t]$$

Lo que implica que es posible que sin otros efectos en la jerarquía.$\mathrm{FPT} = \mathrm{W}[t-1]$

Referencias

1. J. Flum y M. Grohe, "Teoría de la complejidad parametrizada", Springer, 2006.
2. R. Downey y M. Fellows, "Fundamentos de la teoría de la complejidad parametrizada", Springer, 2014.