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

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

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

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

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

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

<p>This is also preceded by:</p>

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

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

<p><strong>References:</strong></p>

<ol>
<li>J. Flum and M. Grohe, "Parameterized Complexity Theory", Springer, 2006.</li>
<li>R. Downey and M. Fellows, "Fundamentals of Parameterized Complexity Theory", Springer, 2014.</li>
</ol>

CC BY-SA 3.0
2015-04-08T05:13:32.393Z
2015-04-08T15:34:59.853Z
2015-04-08T15:34:59.853Z
Luke Mathieson
<p>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.</p>

<p>If $\mathsf{FPT}=\mathsf{W}[P]$ then $\mathsf{P}=\mathsf{W}[P]$.</p>

<p>But does it follow that </p>

<ul>
<li>If $\mathsf{FPT}=\mathsf{W}[1]$ then $\mathsf{FPT}=\mathsf{W}[P]$ ?
or</li>
<li>If $\mathsf{W}[t-1]=\mathsf{W}[t]$ (for some t) then $\mathsf{FPT}=\mathsf{W}[P]$ ?</li>
</ul>

CC BY-SA 3.0
2011-09-04T13:13:02.893Z
What does the "W[]" notation mean?
Tyson Williams
CC BY-SA 3.0
2011-09-04T14:04:20.657Z
Does the second question mean "for all t" or "for some t"?
Yoshio Okamoto
CC BY-SA 3.0
2011-09-04T19:19:29.080Z
The second question mean "for some t"
Uéverton dos santos souza
CC BY-SA 3.0
2011-09-06T15:25:05.797Z
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
CC BY-SA 3.0
2011-09-07T22:02:50.210Z
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
<cc.complexity-theory><parameterized-complexity><fixed-parameter-tractable>
FPT vs W[P] - Parameterized Complexity
Uéverton dos santos souza
# FPT vs W[P] - Parameterized Complexity

(Asked by: username_0 on 2011-09-04)

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

**Tags:** cc.complexity-theory, parameterized-complexity, fixed-parameter-tractable
> **Comments:**
> **username_1**: What does the "W[]" notation mean?  
> **username_2**: Does the second question mean "for all t" or "for some t"?  
> **username_0**: The second question mean "for some t"  
> **username_3**: 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.  
> **username_0**: 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.**  

---

## 1 answers

### Answer by username_4 on 2015-04-08. Score: 16 | Accepted answer

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.


---

