¿Cuál es la motivación detrás de la definición de trazabilidad de parámetros fijos?

FPT contiene los problemas manejables del parámetro fijo, que son aquellos que pueden resolverse en el tiempo para alguna función computable . Por lo general, esta función se considera exponencial simple, como pero la definición admite funciones que crecen aún más rápido. Esto es esencial para gran parte de la historia temprana de esta clase. La parte crucial de la definición es excluir funciones de la forma , como $f(k)\cdot|x|^{O(1)}$ $f$ $2^{O(k)}$ $f(n,k)$ $n^k$ .

Pregunta : ¿Cuál es la motivación detrás de esta definición?

Lo que me desconcierta es que, si es fijo (según "trazabilidad de parámetro fijo"), entonces es un polinomio en . Entonces, ¿por qué es crucial excluir ? $k$ $n^k$ $n$ $n^k$

cc.complexity-theory fixed-parameter-tractable Douglas S. Stones
fuente

n^{k}

$n^k$

n \approx 1000000

$n ≈ 1000000$

k \approx 30

$k ≈ 30$

n^{k}

$n^k$

n

$n$

@JukkaSuomela: Creo que tu comentario podría ser una respuesta.

Suresh Venkat

Respuestas:

$n$ $k$

$n$ $2^k n^2$ $k^2 n^k$ $k$ $n$ creciente. Esta intuición es apoyada tanto en la práctica como en la teoría; es decir, los problemas de FPT tienden a ser notablemente más manejables en la práctica que los problemas arbitrarios de XP, y también se puede obtener una buena imagen teórica de la estructura de XP al comenzar con FPT en la parte inferior y construir jerarquías de otras subclases de XP (como el W jerarquía) por encima de él.

Timothy Chow
fuente