Nom de la sous-classe «uniformément polynomiale» de XP?

Supposons que est un langage paramétré par rapport à un alphabet . La tranche de est , l'ensemble des instances de qui ont le paramètre . La classe de complexité contient les langages paramétrés tels que pour chaque , éventuellement avec un algorithme différent et un temps d'exécution polynomial lié pour chaque . Chaque langue traitable à paramètres fixes est dans , et il y a des langues dans $L$ $\Sigma$ $k$ $L$ $L_k = L \cap \{(x,k) \mid x \in \Sigma^{*}\}$ $L$ $k$ $\mathsf{XP}$ $L$ $L_k \in P$ $k$ $k$ $\mathsf{XP}$ $\mathsf{XP}$ qui ne sont pas dans ; il s'agit de la proposition 27.1.1 du manuel Downey & Fellows 2013. $\mathsf{FPT}$

Cependant, semble avoir une structure non triviale au-delà de cela, car on peut stratifier cette classe en fonction de la vitesse à laquelle le degré du polynôme englobant croît avec : pour le degré est constant, alors que pour il peut croître arbitrairement. Downey & Fellows ne mentionne rien sur la structure de au-delà de la proposition 27.1.1, et la discussion dans le manuel Flum & Grohe 2006 n'est pas beaucoup plus détaillée. $\mathsf{XP}$ $k$ $\mathsf{FPT}$ $\mathsf{XP}$ $\mathsf{XP}$

Dans le prolongement de ma question précédente Limites des variantes de l'ensemble indépendant? existe-t-il un nom pour la sous-classe de où s'il existe un polynôme tel que chaque instance dans peut être décidée au plus étapes? $\mathsf{Q}$ $\mathsf{XP}$ $L \in \mathsf{Q}$ $g_L$ $(x,k)$ $L$ $|x|^{g_L(k)}$

En d'autres termes, cette classe n'autorise que jusqu'à heure au lieu de heure pour une fonction arbitraire comme pour . $\mathsf{Q}$ $|x|^{\text{poly}(k)}$ $|x|^{g(k)}$ $g$ $\mathsf{XP}$

cc.complexity-theory reference-request parameterized-complexity András Salamon
la source

C'est une excellente question! Je suis en fait très intéressé par la sous-classe où le polynôme est linéaire. Autrement dit, Q n'autorise que jusqu'à .

| x |^{O (k)}

$\vert x \vert ^{O(k)}$

Michael Wehar

Réponses:

Je ne pense pas que cette sous-classe de ait été étudiée dans la littérature (et ait reçu un nom). $\textsf{XP}$

L'une des raisons pour lesquelles les chercheurs pourraient hésiter à étudier cette sous-classe, c'est qu'elle n'est pas fermée en raison de réductions fpt (et il faudrait donc faire face à un nouveau type de réductions «ennuyeux»). En effet, les réductions fpt permettent à la valeur du paramètre de exploser de manière superpolynomiale (tant qu'elle est limitée par une fonction calculable de l'ancienne valeur du paramètre). Pour obtenir une notion restreinte de réductions fpt sous lesquelles votre sous-classe de est fermée, vous devez ajouter la restriction selon laquelle les réductions fpt nécessitent que la nouvelle valeur de paramètre soit limitée par un polynôme de l'ancienne valeur de paramètre. $\textsf{XP}$

Ronald de Haan
la source

Les réductions dont vous parlez ont été étudiées dans le contexte de la kernlizaiton sous le nom de "transformations de paramètres polynomiaux", mais elles doivent s'exécuter en temps polynomial.

daniello

Je pense subjectivement qu'un nouveau type de réduction pourrait être bon (pas très gênant). J'ai toujours été sceptique quant aux réductions de fpt permettant à

d'être illimité.

g (k)

$g(k)$

Michael Wehar

J'ai vu deux notions de réduction linéaire de fpt dans la littérature qui nécessitent que

soit borné.

g (k)

$g(k)$

Michael Wehar