Why do we care about computable functions in parametrized complexity definitions?

Question

In a classical definition of the FPT complexity class, for a parametrized problem $L\subseteq \Sigma^* \times \mathbb{N}$ we require an algorithm, solving an instance $(G,k)$ in time $f(k)\cdot n^{O(1)}$, where $f$ is a computable function.

Very simillarly, there is a notion of parametrized reduction, where we require an algorithm running in fpt-time transforming instance $(G,k)$ to instance $(G',k')$ and it holds that $k'\leq g(k)$ for some computable function $g$.

And so on.

It is good to note that some straightforward observations about reductions or FPT properties are true because composition of computable functions is computable.

For example the observation: If $P\leq_{\operatorname{fpt}}Q$ and $Q$ is FPT, then $P$ is FPT. Or this one: If $P\leq_{\operatorname{fpt}}Q$ and $Q\leq_{\operatorname{fpt}}R$, then $P\leq_{\operatorname{fpt}}R$.

My question is, why do we care that much so that the functions are computable? If i denote by $\sigma$ the busy beaver function, which is a familiar example of non-computable function, what would be the issue to have an algorithm with running time, say $\sigma(k)\cdot n^2$ ?

I know there is simillar notion of time- and space- constructible functions, which are required in hierarchy theorems and we indeed need the assumption that we can count $f(k)$ on some Turing machine in $O(f(k))$ time/space. But the assumption of computability in parametrized complexity seems superfluous to me.

Answer 1

Definitions

Actually, there are three definitions of FPT, already in the Downey/Fellows book.

• The definition you cite is known as strongly uniform FPT.
• Dropping the computability requirement on $f$ (as you suggest) gives weakly uniform FPT.
• For nonuniform FPT, one requires an exponent $c$ and, for each $k$, an $O(n^c)$ algorithm solving instances of the form $(G,k)$. (The algorithms for different $k$ are allowed to be unrelated to each other.)

I don't have the book at hand. Yet I seem to recall that it proves that all three classes are, in fact, different.

For each of these definitions, there is a corresponding notion of reductions. The reducability notions are contained in each other the same way the FPT notions are.

Tractability

I know of two natural ways to obtain tractability results.

• Provide a (uniform) algorithm and analyze its run-time. Likely, the analysis gives $f$ in a form that is clearly computable. Hence strongly uniform FPT. For example, the bounded-search-tree algorithm for parameterized vertex cover has $f(k)=2^k$.
• Use a meta-theorem. Let's consider parameterized vertex cover again. For each $k$, let $C_k$ be the class of graphs that admit a vertex cover of size at most $k$. It is easy to see that $C_k$ is closed under taking graph minors. A theorem by Robertson and Seymour then implies that $C_k$ is decidable in time $O(n^3)$. Hence non-uniform FPT.

As noted above, I believe the Downey/Fellows book provides a problem in weakly uniform FPT that they prove not to be in strongly uniform FPT. Yet that is not a natural problem. Also, I would be unlikely to use such an algorithm in practice. The same goes for an algorithm which doesn't have a better bound than $\sigma(k)\cdot n^2$.

Showing that a problem is in strongly uniform FPT is a better (in the sense of stronger) result than showing it to be in weakly uniform FPT. As the technique used to prove the latter can usually be adapted to prove the former as well, that is what is being done.

Intractability

Absolute intractability can be proved, for example, with diagonalization. Most of the time, however, we need to contend with relative intractability: If the problem at hand would be tractable, then so would be a famous other problem that is already believed to be intractable. The standard tool for relative intractability are reductions.

Again, the result is the better, the more restrictive the notion of reduction is. Hence strongly uniform FPT reductions are favoured over weakly uniform ones.

Summary

If strongly uniform FPT had never been defined, we now would have largely the same picture, just that the notion of weakly uniform FPT would be used throughout. As you seem to suggest. The results we do have (using the notion of strongly uniform FPT and respective reductions) are stronger, and hence favourable from a technical perspective.

Side note: The notion of bounded fixed parameter tractability has been proposed, in which the function $f$ is restricted further. See, for example, the Flum/Grohe book.