21

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]$.

But does it follow that

  • 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]$ ?
Uéverton dos santos souza
  • 213
  • 1
  • 6
  • 1
    What does the "W[]" notation mean? – Tyson Williams Sep 04 '11 at 13:13
  • 1
    Does the second question mean "for all t" or "for some t"? – Yoshio Okamoto Sep 04 '11 at 14:04
  • The second question mean "for some t" – Uéverton dos santos souza Sep 04 '11 at 19:19
  • 2
    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 06 '11 at 15:25
  • 2
    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 07 '11 at 22:02

1 Answers1

15

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.
Huck Bennett
  • 4,868
  • 2
  • 33
  • 46
Luke Mathieson
  • 1,178
  • 11
  • 21