<p>If you require only that the growth rate be a polynomial in $n$ for fixed $k$, then you get the definition of the parameterized complexity class XP, which is certainly an object of interest, so there's nothing wrong with considering it.</p>

<p>You get the definition of FPT if you further impose the condition that the <i>degree</i> of the polynomial in $n$ <i>remains fixed</i> as the parameter increases.  FPT turns out to be a particularly tractable subclass of XP, and intuitively, the reason is that an expression such as $2^k n^2$ doesn't explode as quickly as an expression such as $k^2 n^k$, if $k$ and $n$ are <i>both</i> increasing.  This intuition is supported both in practice and in theory; i.e., FPT problems tend to be noticeably more tractable in practice than arbitrary XP problems, and one can also get a nice theoretical picture of the structure of XP by starting with FPT at the bottom and constructing hierarchies of other subclasses of XP (such as the W hierarchy) above it.</p>

CC BY-SA 3.0
2012-04-20T16:23:08.933Z
2012-04-20T16:23:08.933Z
Timothy Chow
<p><a href="http://en.wikipedia.org/wiki/Parameterized_complexity#FPT">Wikipedia</a> writes:</p>

<blockquote>
  <p>FPT contains the fixed parameter tractable problems, which are those
  that can be solved in time $f(k)\cdot|x|^{O(1)}$ for some computable function $f$. Typically,
  this function is thought of as single exponential, such as $2^{O(k)}$ but the
  definition admits functions that grow even faster. This is essential
  for a large part of the early history of this class. The crucial part
  of the definition is to exclude functions of the form $f(n,k)$, such as $n^k$.</p>
</blockquote>

<p><strong>Question</strong>: What is the motivation behind this definition?</p>

<p>What's puzzling me is that, if $k$ is fixed (as per "fixed parameter tractability"), then $n^k$ is a polynomial in $n$.  So, why is it crucial to exclude $n^k$?</p>

CC BY-SA 3.0
2012-04-14T09:36:07.660Z
Because $n^k$ is often both trivial from a theory perspective and far too slow from a practical perspective. One way to put it is that the FPT business tries to understand the computational complexity of problems for the values of parameters that are in the ballpark of $n ≈ 1000000$ and $k ≈ 30$.
Jukka Suomela
CC BY-SA 3.0
2012-04-14T23:00:51.577Z
Hmm... so, if I understand correctly, if we let $n^k$ into FPT, then we will end up including a bunch of decision problems trivially, via brute-force algorithms.
Douglas S. Stones
CC BY-SA 3.0
2012-04-15T03:15:17.863Z
That's right. Of course there's a hierarchy of fixed parameter problems, and FPT is at the bottom. n^k is at the top. More generally, the idea is to try and separate out the influence of the parameter and the influence of $n$, and hence the two separate parts of the running time.
Suresh Venkat
CC BY-SA 3.0
2012-04-15T03:15:37.520Z
@JukkaSuomela: I think your comment could be made an answer.
Suresh Venkat
<cc.complexity-theory><fixed-parameter-tractable>
What is the motivation behind the definition of fixed parameter tractability?
Douglas S. Stones
# What is the motivation behind the definition of fixed parameter tractability?

(Asked by: username_0 on 2012-04-14)

[Wikipedia](http://en.wikipedia.org/wiki/Parameterized_complexity#FPT) writes:

> FPT contains the fixed parameter tractable problems, which are those
> that can be solved in time $f(k)\cdot|x|^{O(1)}$ for some computable function $f$. Typically,
> this function is thought of as single exponential, such as $2^{O(k)}$ but the
> definition admits functions that grow even faster. This is essential
> for a large part of the early history of this class. The crucial part
> of the definition is to exclude functions of the form $f(n,k)$, such as $n^k$.

**Question**: What is the motivation behind this definition?

What's puzzling me is that, if $k$ is fixed (as per "fixed parameter tractability"), then $n^k$ is a polynomial in $n$. So, why is it crucial to exclude $n^k$?

**Tags:** cc.complexity-theory, fixed-parameter-tractable

> **Comments:**
> **username_1**: Because $n^k$ is often both trivial from a theory perspective and far too slow from a practical perspective. One way to put it is that the FPT business tries to understand the computational complexity of problems for the values of parameters that are in the ballpark of $n ≈ 1000000$ and $k ≈ 30$.  
> **username_0**: Hmm... so, if I understand correctly, if we let $n^k$ into FPT, then we will end up including a bunch of decision problems trivially, via brute-force algorithms.  
> **username_2**: That's right. Of course there's a hierarchy of fixed parameter problems, and FPT is at the bottom. n^k is at the top. More generally, the idea is to try and separate out the influence of the parameter and the influence of $n$, and hence the two separate parts of the running time.  
> **username_2**: @JukkaSuomela: I think your comment could be made an answer.  

---

## 1 answers

### Answer by username_3 on 2012-04-20. Score: 15 | Accepted answer

If you require only that the growth rate be a polynomial in $n$ for fixed $k$, then you get the definition of the parameterized complexity class XP, which is certainly an object of interest, so there's nothing wrong with considering it.

You get the definition of FPT if you further impose the condition that the *degree* of the polynomial in $n$ *remains fixed* as the parameter increases. FPT turns out to be a particularly tractable subclass of XP, and intuitively, the reason is that an expression such as $2^k n^2$ doesn't explode as quickly as an expression such as $k^2 n^k$, if $k$ and $n$ are *both* increasing. This intuition is supported both in practice and in theory; i.e., FPT problems tend to be noticeably more tractable in practice than arbitrary XP problems, and one can also get a nice theoretical picture of the structure of XP by starting with FPT at the bottom and constructing hierarchies of other subclasses of XP (such as the W hierarchy) above it.


---

