FPT vs W [P] - Complexité paramétrée

En complexité paramétrée, ⊆ W [ 2 ] ⊆ … ⊆ W [ P ] . On suppose que chacune des enceintes est appropriée.$\mathsf{FPT} \subseteq \mathsf{W}[1]$ $\subseteq \mathsf{W}[2]$ $\subseteq \ldots \subseteq \mathsf{W}[P]$

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

Mais est-ce qu'il s'ensuit que

• Si alors F P T = W [ P ] ? ou$\mathsf{FPT}=\mathsf{W}[1]$$\mathsf{FPT}=\mathsf{W}[P]$
• Si (pour certains t) alors F P T = W [ P ] ?$\mathsf{W}[t-1]=\mathsf{W}[t]$$\mathsf{FPT}=\mathsf{W}[P]$

Cette question est délicate car la réponse (pour autant que je sache) est toujours "ne sais pas".

Pour ajouter du poids à cela, Flum & Grohe [1] donnent comme problèmes ouverts (p. 164):

• $\mathrm{W}$$\mathrm{FPT} \neq \mathrm{W[P]}$
• $t \geq 1$$\mathrm{W}[t] = \mathrm{W}[t + 1]$$\mathrm{W}[t] = \mathrm{W}[t + 2]$

De plus, dans la récente monographie de Downey et Fellow [2], la déclaration la plus ferme (pure et simple) qu'ils font est (p. 521):

$\mathrm{W}$$\mathrm{W}[1] \neq \mathrm{W}[2]$

$\mathrm{W}$

Ceci est également précédé de:

$t$

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

$\mathrm{FPT} = \mathrm{W}[t-1]$

Les références:

1. J. Flum et M. Grohe, "Parameterized Complexity Theory", Springer, 2006.
2. R. Downey et M. Fellows, «Fundamentals of Parameterized Complexity Theory», Springer, 2014.