<p>I've been researching Parameterized Complexity Theory, and I've been puzzled by the definition of W[P]. Why is the number of non-deterministic steps bounded by $log|n|$? What is the intuition I should have for problems in W[P]?</p>

CC BY-SA 4.0
2018-05-08T06:29:11.697Z
So there is this common theme in existence problems.  You have a set with $n$ elements and you want to know if there exists of a subset of size $k$ satisfying some property that you can verify in polynomial time.  This is the kind of problem that we can quickly say is in $W[P]$.  You non-deterministically guess the subset of size $k$ (which requires at most $k \log(n)$ non-deterministic bits) and then you in polynomial time verify if it satisfies the desired property.
Michael Wehar
CC BY-SA 4.0
2018-05-08T06:34:17.483Z
I've found very few problems that are hard for $W[P]$, but there are a lot of problems where you can fairly easily say, that's in $W[P]$.  Most of these problems that I encounter, on further inspection, end up being in $W[1]$ or $W[2]$ which are much lower down in the parameterized complexity hierarchy than $W[P]$.
Michael Wehar
CC BY-SA 4.0
2018-05-08T06:37:35.743Z
It seems easier for me to find hard problems for $W[NL]$ and $W[L]$ than for $W[P]$ because most verifiers that I come up with end up being not only polynomial time computable, but also logspace computable.
Michael Wehar
CC BY-SA 4.0
2018-05-08T06:39:29.457Z
This is kind of like the situation where many (if not all) of the NP-complete problems that are commonly discussed are NP-complete relative to logspace many-one reductions.
Michael Wehar
<cc.complexity-theory><parameterized-complexity>
What is the motivation behind W[P]?
Samuel Barr
# What is the motivation behind W[P]?

(Asked by: username_0 on 2018-05-08)

I've been researching Parameterized Complexity Theory, and I've been puzzled by the definition of W[P]. Why is the number of non-deterministic steps bounded by $log|n|$? What is the intuition I should have for problems in W[P]?

**Tags:** cc.complexity-theory, parameterized-complexity

> **Comments:**
> **username_1**: So there is this common theme in existence problems.  You have a set with $n$ elements and you want to know if there exists of a subset of size $k$ satisfying some property that you can verify in polynomial time.  This is the kind of problem that we can quickly say is in $W[P]$.  You non-deterministically guess the subset of size $k$ (which requires at most $k \log(n)$ non-deterministic bits) and then you in polynomial time verify if it satisfies the desired property.  
> **username_1**: I've found very few problems that are hard for $W[P]$, but there are a lot of problems where you can fairly easily say, that's in $W[P]$.  Most of these problems that I encounter, on further inspection, end up being in $W[1]$ or $W[2]$ which are much lower down in the parameterized complexity hierarchy than $W[P]$.  
> **username_1**: It seems easier for me to find hard problems for $W[NL]$ and $W[L]$ than for $W[P]$ because most verifiers that I come up with end up being not only polynomial time computable, but also logspace computable.  
> **username_1**: This is kind of like the situation where many (if not all) of the NP-complete problems that are commonly discussed are NP-complete relative to logspace many-one reductions.  

---

## 0 answers

