# Name for “uniformly polynomial” subclass of XP?

Suppose $L$ is a parameterized language with respect to some alphabet $\Sigma$. The $k$-slice of $L$ is $L_k = L \cap \{(x,k) \mid x \in \Sigma^{*}\}$, the set of instances in $L$ which have parameter $k$. The complexity class $\mathsf{XP}$ contains the parameterized languages $L$ such that $L_k \in P$ for each $k$, possibly with a different algorithm and polynomial running time bound for each $k$. Each fixed-parameter tractable language is in $\mathsf{XP}$, and there are languages in $\mathsf{XP}$ that are not in $\mathsf{FPT}$; this is Proposition 27.1.1 in the Downey & Fellows 2013 textbook.

However, $\mathsf{XP}$ seems to have nontrivial structure beyond this, since one can stratify this class based on how fast the degree of the bounding polynomial grows with $k$: for $\mathsf{FPT}$ the degree is constant, whereas for $\mathsf{XP}$ it can grow arbitrarily. Downey & Fellows does not mention anything about the structure of $\mathsf{XP}$ beyond Proposition 27.1.1, and the discussion in the Flum & Grohe 2006 textbook isn't much more detailed.

Following on from my earlier question Limits of variants of Independent Set? is there a name for the subclass $\mathsf{Q}$ of $\mathsf{XP}$ where $L \in \mathsf{Q}$ if there is a polynomial $g_L$ such that every instance $(x,k)$ in $L$ can be decided in at most $|x|^{g_L(k)}$ steps?

In other words, this class $\mathsf{Q}$ allows only up to $|x|^{\text{poly}(k)}$ time instead of $|x|^{g(k)}$ time for some arbitrary function $g$ as for $\mathsf{XP}$.

• This is a great question! I'm actually very interested in the subclass where the polynomial is linear. That is, Q allows only up to $\vert x \vert ^{O(k)}$. – Michael Wehar May 26 '17 at 4:51

I don't think this subclass of $\textsf{XP}$ has been studied in the literature (and given a name).
One reason why researchers might shy away from studying this subclass, is that it is not closed under fpt-reductions (and so one would have to deal with an 'annoying' new type of reductions). This is because fpt-reductions allow the parameter value to blow up superpolynomially (as long as it is bounded by some computable function of the old parameter value). To get a restricted notion of fpt-reductions under which your subclass of $\textsf{XP}$ is closed, you would need to add the restriction that fpt-reductions require the new parameter value to be bounded by some polynomial of the old parameter value.
• I subjectively think that a new type of reduction could be good (not very annoying). I've always been skeptical of fpt-reductions allowing for $g(k)$ to be unbounded. – Michael Wehar Jul 16 '17 at 8:05
• I've seen two notions of linear fpt-reduction in the literature that require $g(k)$ to be bounded. – Michael Wehar Jul 16 '17 at 8:06