3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Raphael Jun 9 '17 at 4:50
  • $\begingroup$ XP stands for "slice-wise polynomial". $\endgroup$ – Juho Jun 9 '17 at 5:30
4
$\begingroup$

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.

$\endgroup$

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.