20
$\begingroup$

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

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.
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.