# FPT vs W[P] - Parameterized Complexity

In parametrized complexity, $\mathsf{FPT} \subseteq \mathsf{W}[1]$ $\subseteq \mathsf{W}[2]$ $\subseteq \ldots \subseteq \mathsf{W}[P]$. It is conjectured that each of the containments is proper.

If $\mathsf{FPT}=\mathsf{W}[P]$ then $\mathsf{P}=\mathsf{W}[P]$.

• If $\mathsf{FPT}=\mathsf{W}[1]$ then $\mathsf{FPT}=\mathsf{W}[P]$ ? or
• If $\mathsf{W}[t-1]=\mathsf{W}[t]$ (for some t) then $\mathsf{FPT}=\mathsf{W}[P]$ ?
• What does the "W[]" notation mean? – Tyson Williams Sep 4 '11 at 13:13
• Does the second question mean "for all t" or "for some t"? – Yoshio Okamoto Sep 4 '11 at 14:04
• The second question mean "for some t" – Uéverton dos santos souza Sep 4 '11 at 19:19
• You are not being a helpful question-asker. You haven't included definition or links to the W-hierarchy, even though someone asked you about that. The answer to your questions is probably "both are open," because of the W-hierarchy's characterization as families of modified AC0 circuits -- a collapse of the W-hierarchy would imply a circuit complexity collapse. (This is considered evidence that every level of the W-hierarchy is a proper subset of the next.) But I would have to check some things to post an answer (not my area), and you are not taking the question seriously. – Aaron Sterling Sep 6 '11 at 15:25
• A parameterized problem (L,K) belongs to W[t] if there exists k' computed from k such that (L,K) reduces to the weight-k' satisability problem for weft-t circuits. [Downey, 1997] [Downey, 1997] Rodney G. Downey, Michael R. Fellows, Kenneth W. Regan; Research Report Series Parameterized Circuit Complexity and the W Hierarchy; Centre for Discrete Mathematics and Theoretical Computer Science; 1997. – Uéverton dos santos souza Sep 7 '11 at 22:02

This question is tricky as the answer (as far as I know) is still "don't know".

To add some weight to this, Flum & Grohe [1] give as open problems (p. 164):

• Is the $\mathrm{W}$-hierarchy strict under the assumption $\mathrm{FPT} \neq \mathrm{W[P]}$?
• For $t \geq 1$, does the equality $\mathrm{W}[t] = \mathrm{W}[t + 1]$ imply $\mathrm{W}[t] = \mathrm{W}[t + 2]$?

Moreover, in Downey and Fellow's recent monograph [2] the strongest (outright) statement they make is (p. 521):

A more subtle hypothesis is that the $\mathrm{W}$-hierarchy is proper, and, in particular, $\mathrm{W}[1] \neq \mathrm{W}[2]$.

There is no following (or later) statement along the lines "otherwise the $\mathrm{W}$-hierarchy would collapse", or similar.

This is also preceded by:

A weaker hypothesis might be that for some $t$, $$\mathrm{FPT} \neq \mathrm{W}[t]$$

Implying that it is possible that $\mathrm{FPT} = \mathrm{W}[t-1]$ with no other effects on the hierarchy.

References:

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