What does the complexity class $\mathsf{XP}$ stand for?

Question

$\mathsf{XP}$ is the class of problems with input length $n$ and parameter $k$ than can be solved in $O(n^{f(k)})$ time, where $f$ is a computable function. It's described on the complexity zoo page as "Fixed-parameter Tractable for Each Parameter", but I fail to see how adding "for each parameter" to the description causes such a significant change to the definition compared to $\mathsf{FPT}$, which contains problems solvable in $O(f(k)\cdot n^{O(1)})$ time.

The complexity zoo page mentions the book it was defined in, Parameterized Complexity, but I don't have access to it right now.

Answer 1

There is a slightly different description for XP which I personally find less misleading: "Polynomial time for each parameter". I believe the zoo page uses FPT instead of P for some formal reasons (parameterized problems are sometimes defined as subsets of $\Sigma^*\times\Pi^*$, classical problems as subsets of $\Sigma^*$). It can be noted that both formulations describe non-uniform XP, while the time bound $O(n^{f(k)})$ refers to uniform XP. In any case, the important difference is that for XP, the exponent of $n$ may depend on the parameter, for FPT it mustn't.

The practical importance of XP is as a door to parameterized complexity analysis. Once a problem is recognized as belonging to XP it makes sense to investigate its exact parameterized complexity. If it does not even belong to XP, parameterized analysis doesn't make much sense. It can also be argued that in that case the parameterization is not meaningful.

Answer 2

FPT stands for fixed-parameter tractable, and is the class of parameterized problems solvable in time $$f(k) \cdot n^{O(1)},$$ for any function $f$. A parameterized problem is a problem that comes with a specific parameter that you may use exponential time in, or that we are particularly interested in. Examples of parameterized problems are Vertex Cover parameterized by solution size, Independent Set parameterized by solution size, coloring parameterized by number of colors, etc. Only the first of these belong to FPT, where as the second belong to a class W[1] (if you're going to ask, W is short for weft, don't ask).

There are few problems that make sense to cite as being in XP. XP is "short" for slice-wise polynomial, and is the class of problems solvable in time $O(n^{f(k)})$. Note that coloring cannot be in XP (unless P = NP) since then 3-coloring (which is NP-complete) would be solvable in $O(n^{f(3)}) = O(n^c)$ time, thus rendering it polynomially solvable.

(Cross-posted from What does FTP and XP stand for.)