Wikipedia 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$?
What is the motivation behind the definition of fixed parameter tractability?
cc.complexity theory;fixed parameter tractable
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.