¿Nombre de la subclase de XP "uniformemente polinomial"?

Supongamos que es un lenguaje parametrizado con respecto a algún alfabeto . La división de es , el conjunto de instancias en que tienen el parámetro . La clase de complejidad contiene los lenguajes parametrizados modo que para cada , posiblemente con un algoritmo diferente y un tiempo de ejecución polinómico limitado para cada . Cada idioma manejable de parámetros fijos está en , y hay idiomas en $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}$ que no están en ; Esta es la Proposición 27.1.1 del libro de texto Downey & Fellows 2013. $\mathsf{FPT}$

Sin embargo, parece tener una estructura no trivial más allá de esto, ya que uno puede estratificar esta clase en función de qué tan rápido crece el grado del polinomio delimitador con : para el grado es constante, mientras que para puede crecer arbitrariamente. Downey & Fellows no menciona nada sobre la estructura de más allá de la Proposición 27.1.1, y la discusión en el libro de texto de Flum & Grohe 2006 no es mucho más detallada. $\mathsf{XP}$ $k$ $\mathsf{FPT}$ $\mathsf{XP}$ $\mathsf{XP}$

Siguiendo con mi pregunta anterior ¿ Límites de variantes de conjunto independiente? ¿hay un nombre para la subclase de donde si hay un polinomio tal que cada instancia en pueda decidirse como máximo pasos? $\mathsf{Q}$ $\mathsf{XP}$ $L \in \mathsf{Q}$ $g_L$ $(x,k)$ $L$ $|x|^{g_L(k)}$

En otras palabras, esta clase permite solo hasta tiempo en lugar de tiempo para alguna función arbitraria como para . $\mathsf{Q}$ $|x|^{\text{poly}(k)}$ $|x|^{g(k)}$ $g$ $\mathsf{XP}$

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

¡Esta es una gran pregunta! De hecho, estoy muy interesado en la subclase donde el polinomio es lineal. Es decir, Q permite solo hasta .

| x |^{O (k)}

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

Michael Wehar

Respuestas:

No creo que esta subclase de haya sido estudiada en la literatura (y haya recibido un nombre). $\textsf{XP}$

Una de las razones por las cuales los investigadores podrían evitar estudiar esta subclase es que no está cerrada bajo fpt-reducciones (por lo que uno tendría que lidiar con un nuevo tipo de reducciones 'molestas'). Esto se debe a que las reducciones de fpt permiten que el valor del parámetro explote superpolinomialmente (siempre que esté limitado por alguna función computable del valor del parámetro anterior). Para obtener una noción restringida de fpt-reducciones bajo la cual su subclase de está cerrada, necesitará agregar la restricción de que fpt-reductions requiere que el nuevo valor del parámetro esté limitado por algún polinomio del valor del parámetro anterior. $\textsf{XP}$

Ronald de Haan
fuente

Las reducciones de las que habla se han estudiado en el contexto de kernlizaiton bajo el nombre de "transformaciones de parámetros polinomiales", sin embargo, estas deben ejecutarse en tiempo polinomial.

daniello

Subjetivamente pienso que un nuevo tipo de reducción podría ser bueno (no muy molesto). Siempre he sido escéptico de las reducciones de fpt que permiten que sea ilimitado.

g (k)

$g(k)$

Michael Wehar

He visto dos nociones de reducción lineal de fpt en la literatura que requieren que esté limitado.

g (k)

$g(k)$

Michael Wehar