FPT против W [P] - Параметризованная сложность

В параметризованной сложности, . Предполагается, что каждое из условий является правильным.⊆ W [ 2 ] ⊆ … ⊆ W [ P $\mathsf{FPT} \subseteq \mathsf{W}[1]$ $\subseteq \mathsf{W}[2]$ $\subseteq \ldots \subseteq \mathsf{W}[P]$

Если то .P = W [ P $\mathsf{FPT}=\mathsf{W}[P]$$\mathsf{P}=\mathsf{W}[P]$

Но следует ли это

• Если то ? илиF P T = W [ P $\mathsf{FPT}=\mathsf{W}[1]$$\mathsf{FPT}=\mathsf{W}[P]$
• Если (для некоторого t), то ?F P T = W [ P $\mathsf{W}[t-1]=\mathsf{W}[t]$$\mathsf{FPT}=\mathsf{W}[P]$

Этот вопрос сложен, поскольку ответ (насколько я знаю) все еще "не знаю".

Чтобы добавить к этому некоторый вес, Flum & Grohe [1] дают открытые задачи (стр. 164):

• Является ли иерархия строгой в предположении F P T ≠ W [ P ] ?$\mathrm{W}$$\mathrm{FPT} \neq \mathrm{W[P]}$
• При из равенства 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]$

Более того, в недавней монографии Дауни и Феллоу [2] самое сильное (прямое) утверждение, которое они делают, это (стр. 521):

Более тонкая гипотеза состоит в том, что иерархия правильная, и, в частности, W [ 1 ] ≠ W [ 2 ] .$\mathrm{W}$$\mathrm{W}[1] \neq \mathrm{W}[2]$

Не существует следующего (или более позднего) утверждения в отношении «иначе иерархия рухнет» или подобного.$\mathrm{W}$

Этому также предшествует:

Более слабая гипотеза может быть то , что в течение некоторого , Р Р Т ≠ W [ T $t$

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

Подразумевается, что возможно, что без каких-либо других воздействий на иерархию.$\mathrm{FPT} = \mathrm{W}[t-1]$

Ссылки:

1. Дж. Флум и М. Гроэ, «Теория параметризованной сложности», Springer, 2006.
2. R. Downey и M. Fellows, «Основы теории параметризованной сложности», Springer, 2014.