FPT vs W [P] - sparametryzowana złożoność

W sparametryzowanej złożoności ⊆ W [ 2 ] ⊆ … ⊆ W [ P ] . Przypuszcza się, że każda zawartość jest właściwa.$\mathsf{FPT} \subseteq \mathsf{W}[1]$ $\subseteq \mathsf{W}[2]$ $\subseteq \ldots \subseteq \mathsf{W}[P]$

Jeśli to P = W [ P ] .$\mathsf{FPT}=\mathsf{W}[P]$$\mathsf{P}=\mathsf{W}[P]$

Ale czy to wynika z tego

• Jeśli to F P T = W [ P ] ? lub$\mathsf{FPT}=\mathsf{W}[1]$$\mathsf{FPT}=\mathsf{W}[P]$
• Jeśli (dla niektórych t) to F P T = W [ P ] ?$\mathsf{W}[t-1]=\mathsf{W}[t]$$\mathsf{FPT}=\mathsf{W}[P]$

To pytanie jest trudne, ponieważ odpowiedź (o ile wiem) wciąż brzmi „nie wiem”.

Aby dodać do tego trochę wagi, Flum i Grohe [1] podają jako otwarte problemy (s. 164):

• Czy hierarchia jest ścisła przy założeniu F P T ≠ W [ P ] ?$\mathrm{W}$$\mathrm{FPT} \neq \mathrm{W[P]}$
• Czy dla równość W [ t ] = W [ t + 1 ] oznacza W [ t ] = W [ t + 2 ] ?$t \geq 1$$\mathrm{W}[t] = \mathrm{W}[t + 1]$$\mathrm{W}[t] = \mathrm{W}[t + 2]$

Co więcej, w najnowszej monografii Downey i Fellow [2] najsilniejszym (wprost) stwierdzeniem, jakie piszą jest (s. 521):

Bardziej subtelna hipoteza jest taka, że hierarchia jest poprawna, aw szczególności W [ 1 ] ≠ W [ 2 ] .$\mathrm{W}$$\mathrm{W}[1] \neq \mathrm{W}[2]$

Nie ma następującej (lub późniejszej) instrukcji w stylu „inaczej hierarchia zawaliłaby się” lub podobnie.$\mathrm{W}$

Poprzedza to również:

Słabszą hipotezą może być to, że dla niektórych , F P T ≠ W [ t $t$

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

Sugeruje to, że bez innych skutków dla hierarchii.$\mathrm{FPT} = \mathrm{W}[t-1]$

Bibliografia:

1. J. Flum i M. Grohe, „Parameterized Complexity Theory”, Springer, 2006.
2. R. Downey i M. Fellows, „Podstawy sparametryzowanej teorii złożoności”, Springer, 2014.