# Proving FPT is strictly contained in XP

In their book Fundamentals of Parameterized Complexity, Downey and Fellows claim (in chapter 27.1) that $$\mathrm{FPT}\subsetneq \mathrm{XP}$$, and that this is a "basic result" that follows by "standard diagonalization", without any further reference.

I have neither been able to find a proof of this "basic result" in the literature (although many state it as a basic fact without reference), nor am I familiar enough with the "standard diagonalization" technique to easily produce a proof on my own.

Is there a full proof or more detailed sketch available in the literature? Alternatively, can you provide such a proof or sketch here? I suppose this diagonalization technique would be a basic tool in complexity theory, so looking near that field might be useful.

By the time hierarchy theorem, there is a family of languages $$(L_k)_{k \in \mathbb{N}}$$ such that $$L_k$$ is decidable in time $$O(n^{2^{k+1}})$$, but not in time $$O(n^{2^k})$$. We define $$\mathcal{L} = \{\langle k, w\rangle \mid w \in L_k\}$$, and use $$k$$ as the parameter.
Then $$(\mathcal{L}, k)$$ is in $$\mathrm{XP}$$, as every fixed slice of $$\mathcal{L}$$ is just some language $$L_k$$, which by our choice belongs to $$\mathrm{P}$$. However, if $$(\mathcal{L},k)$$ were fixed-parameter tractable, it would have some $$O(f(k)\cdot n^\ell)$$-decision process. But by fixing the parameter $$k$$ to be $$\ell$$, we'd get a $$O(n^k)$$ algorithm for $$L_k$$, in contradiction to our choice of $$L_k$$.
• @Discretelizard Actually, I'd consider this a diagonalization argument in a broad sense; specifically the fact that we stitch together $\mathcal{L}$ from more and more complex languages inside $\mathrm{P}$. My guess would that this is more or less what Downey and Fellows had in mind.