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

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

• It seems to me that the essential part of the definition is missing. FPT says for some $k$ and it sounds like XP would like to say something for all $k$.
– Raphael
Jun 9, 2017 at 4:50
• XP stands for "slice-wise polynomial".
– Juho
Jun 9, 2017 at 5:30

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