10
$\begingroup$

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

$\endgroup$
  • 7
    $\begingroup$ 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$. $\endgroup$ – Jukka Suomela Apr 14 '12 at 9:36
  • $\begingroup$ 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. $\endgroup$ – Douglas S. Stones Apr 14 '12 at 23:00
  • 5
    $\begingroup$ 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. $\endgroup$ – Suresh Venkat Apr 15 '12 at 3:15
  • 3
    $\begingroup$ @JukkaSuomela: I think your comment could be made an answer. $\endgroup$ – Suresh Venkat Apr 15 '12 at 3:15
15
$\begingroup$

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.

$\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.