Limites élémentaires du paramètre dans la tractabilité à paramètre fixe?

Dans la définition de la tractabilité à paramètres fixes (forts), la limite de temps est une expression de la forme où l'instance d'entrée est avec le paramètre , est un polynôme et est une fonction calculable .

F (k) . p (| X |),

$f(k).p(|x|),$

(x, k)

$(x,k)$

k

$k$

p

$p$

f

$f$

Il est possible de remplacer l'exigence de calculabilité pour par d'autres classes de fonctions, tant que la notion de réduction est restreinte de la même manière. (Par exemple, Flum et Grohe couvrent les familles exponentielles et sous-exponentielles dans les chapitres 15 à 16 de leur manuel, avec les réductions associées de erf et serf.) $f$

Quelqu'un a-t-il étudié la famille des fonctions élémentaires pour le paramètre lié ? $f$

Une fonction élémentaire peut être délimitée au-dessus par une tour fixe d'exponentielles, donc cette classe est fermée sous composition. La croissance du paramètre dans une réduction doit alors également être bornée par une fonction élémentaire.

Il existe des problèmes intéressants de la théorie des automates qui sont traitables à paramètres fixes, mais où la limite du paramètre est non élémentaire (sauf si P = NP, voir Frick et Grohe, doi: 10.1016 / j.apal.2004.01.007 ). Je me demande si quelqu'un a examiné les problèmes traitables à paramètres fixes qui excluent les valeurs fixes du paramètre conduisant à de telles constantes "galactiques" (pour reprendre le terme de Richard Lipton et Ken Regan). En spéculant de manière extravagante, une telle restriction pourrait avoir des liens utiles avec la théorie des modèles finis, comme être caractérisée par un fragment de logique monadique de second ordre qui ne conduit pas aux constantes non élémentaires qui peuvent résulter de l'application du théorème de Courcelle à un fragment avec alternance de quantificateur illimitée.

cc.complexity-theory reference-request fixed-parameter-tractable András Salamon
la source

Voici un exemple de "problèmes intéressants de la théorie des automates qui sont traitables avec des paramètres fixes, mais où la limite des paramètres n'est pas élémentaire".

Suresh Venkat

N P \neq P

$NP\ne P$

Réponses:

Dans sa thèse de doctorat " Modi ﬁ zierte parametrische Komplexitatstheorie ", Mark Weyer a examiné, entre autres, les hiérarchies au sein de FPT par rapport à la fonction f et les réductions entre elles. Il a également mis en relation ces sous-hiérarchies avec des fragments de FO et MSO: le chapitre 6 traite essentiellement de la relation entre FO / MSO (le nombre d'alternances quantifiantes des formules) et la fonction f (w) dans le théorème de Courcelle (w étant la largeur de l'arborescence). Il a considéré à la fois les limites supérieures et inférieures et, en utilisant le cadre de réduction susmentionné entre certaines hiérarchies au sein de FPT, il a pu donner des limites assez strictes. Les examinateurs de la thèse étaient Flum et Grohe.

Malheureusement, la thèse est en allemand, et je ne sais pas si le matériel de sa thèse a été publié dans une revue anglaise. Je suis donc conscient qu'ils pourraient être d'une utilité limitée pour vous, mais néanmoins les références qui y figurent pourraient être un bon point de départ.

Alexander Langer
la source

Merci, n'avait pas pensé à vérifier ces thèses. Cela semble très pertinent pour les applications que j'ai mentionnées. Il me manque probablement quelque chose, mais à part une brève mention à la page 69, les limites des paramètres élémentaires ne semblent pas intéresser Weyer.

András Salamon,

E_{t}

$\mathcal E_t$

{Q E}_{t}

$\mathcal{QE}_t$

{P E}_{t}

$\mathcal{PE}_t$

t

$t$

e x p^{t} (\cdot)

$exp^t(\cdot)$

Alexander Langer

Pour les bornes élémentaires, il suffit de considérer l'union de toutes les fonctions exponentielles. Ceci est mentionné par Weyer à la page 69 de sa thèse, mais la question ne semble pas être traitée plus avant.

András Salamon,