¿Límites elementales en el parámetro en la trazabilidad de parámetros fijos?

En la definición de rastreabilidad de parámetros fijos (fuertes), el límite de tiempo es una expresión de la forma donde la instancia de entrada es con el parámetro , es un polinomio es una función computable .

F (k) . pag (El | X El |),

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

(x, k)

$(x,k)$

k

$k$

p

$p$

f

$f$

Es posible reemplazar el requisito de computabilidad para con otras clases de funciones, siempre que la noción de reducción esté igualmente restringida. (Por ejemplo, Flum y Grohe cubren familias exponenciales y subexponenciales en los capítulos 15–16 de su libro de texto, con las reducciones asociadas de erf y serf). $f$

¿Alguien ha estudiado la familia de funciones elementales para el parámetro enlazado ? $f$

Una función elemental puede estar limitada anteriormente por una torre fija de exponenciales, por lo que esta clase está cerrada por composición. El crecimiento en el parámetro en una reducción debe estar limitado también por una función elemental.

Existen problemas interesantes de la teoría de autómatas que son manejables con parámetros fijos, pero donde el límite de parámetros no es elemental (a menos que P = NP, ver Frick y Grohe, doi: 10.1016 / j.apal.2004.01.007 ). Me pregunto si alguien ha analizado los problemas manejables de parámetros fijos que excluyen los valores fijos del parámetro que conduce a tales constantes "galácticas" (para usar el término de Richard Lipton y Ken Regan). Especulando salvajemente, tal restricción podría tener conexiones útiles con la teoría de modelos finitos, como ser caracterizada por un fragmento de lógica monádica de segundo orden que no conduce a las constantes no elementales que pueden surgir al aplicar el Teorema de Courcelle a un fragmento con Alternador de alternancia ilimitado.

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

¿Cuál es un ejemplo de "problemas interesantes de la teoría de autómatas que son manejables con parámetros fijos, pero donde el límite de parámetros no es elemental"?

Suresh Venkat

N P \neq P

$NP\ne P$

Respuestas:

En su tesis de disertación " Modi ﬁ zierte parametrische Komplexitatstheorie ", Mark Weyer consideró, entre otras cosas, las jerarquías dentro de FPT wrt la función f y las reducciones entre ellas. De hecho, también relacionó estas sub-jerarquías con fragmentos de FO y MSO: el Capítulo 6 trata esencialmente de la relación entre FO / MSO (el número de alternancias cuantificadoras de las fórmulas) y la función f (w) en el teorema de Courcelle (w siendo el ancho del árbol). Consideró los límites superior e inferior y, utilizando el marco de reducción mencionado anteriormente entre ciertas jerarquías dentro del FPT, pudo establecer límites bastante estrechos. Los examinadores de la tesis fueron Flum y Grohe.

Lamentablemente, la tesis está en alemán, y no sé si el material de su tesis ha sido publicado en una revista inglesa. Por lo tanto, soy consciente de que pueden ser de uso limitado para usted, pero sin embargo, las referencias allí pueden ser un buen punto de partida.

Alexander Langer
fuente

Gracias, no había pensado revisar tesis. Esto parece muy relevante para las aplicaciones que mencioné. Probablemente me falta algo, pero aparte de una breve mención en la página 69, los límites de los parámetros elementales no parecen ser de interés para 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

Para límites elementales, es suficiente considerar la unión de todas las funciones exponenciales. Weyer menciona esto en la página 69 de su tesis, pero el tema no parece tratarse más.

András Salamon