FPT vs W [P] - Complexidade parametrizada

Na complexidade parametrizada, . É conjecturado que cada uma das contenções é adequada.⊆ W [ 2 ] ⊆ … ⊆ W [ P $\mathsf{FPT} \subseteq \mathsf{W}[1]$ $\subseteq \mathsf{W}[2]$ $\subseteq \ldots \subseteq \mathsf{W}[P]$

Se então .P = W [ P $\mathsf{FPT}=\mathsf{W}[P]$$\mathsf{P}=\mathsf{W}[P]$

Mas segue que

• Se então ? ouF P T = W [ P $\mathsf{FPT}=\mathsf{W}[1]$$\mathsf{FPT}=\mathsf{W}[P]$
• Se (para alguns t), então ?F P T = W [ P $\mathsf{W}[t-1]=\mathsf{W}[t]$$\mathsf{FPT}=\mathsf{W}[P]$

Essa pergunta é complicada, pois a resposta (até onde eu sei) ainda é "não sei".

Para acrescentar algum peso a isso, Flum & Grohe [1] apresentam como problemas em aberto (p. 164):

• A hierarquia é estrita sob a suposição ?F P T ≠ W [ P $\mathrm{W}$$\mathrm{FPT} \neq \mathrm{W[P]}$
• Para , a igualdade implica ?W [ t ] = W [ t + 1 ] W [ t ] = W [ t + 2 $t \geq 1$$\mathrm{W}[t] = \mathrm{W}[t + 1]$$\mathrm{W}[t] = \mathrm{W}[t + 2]$

Além disso, na recente monografia de Downey e Fellow [2], a declaração mais forte (direta) que eles fazem é (p. 521):

Uma hipótese mais sutil é que a hierarquia é adequada e, em particular, .W [ 1 ] ≠ W [ 2 $\mathrm{W}$$\mathrm{W}[1] \neq \mathrm{W}[2]$

Não há nenhuma declaração a seguir (ou posterior) ao longo das linhas "caso contrário, a hierarquia entraria em colapso" ou similar.$\mathrm{W}$

Isso também é precedido por:

Uma hipótese mais fraca pode ser que, para alguns , F P T ≠ W [ t $t$

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

Isso implica que é possível que não tenha outros efeitos na hierarquia.$\mathrm{FPT} = \mathrm{W}[t-1]$

Referências:

1. J. Flum e M. Grohe, "Parameterized Complexity Theory", Springer, 2006.
2. R. Downey e M. Fellows, "Fundamentos da teoria da complexidade parametrizada", Springer, 2014.