2
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ This is a very clean proof, thanks. I suppose Downey and Fellows had a proof in mind that would directly use diagonalization, rather than hiding it in the time hierarchy theorem. However, I think I would prefer this approach. It seems more elegant. $\endgroup$
    – Discrete lizard
    Aug 22 at 12:03
  • 1
    $\begingroup$ @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. $\endgroup$
    – Arno
    Aug 22 at 12:10
  • $\begingroup$ Hmm, yes, I suppose that's true as well. I think your guess would be right. $\endgroup$
    – Discrete lizard
    Aug 22 at 12:11

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.