En la complejidad parametrizada, las personas utilizan la reducción de parámetros fijos manejables (FPT) para demostrar la dureza W [t]. Teóricamente, una reducción de FPT no es una reducción de tiempo polinomial, ya que puede ejecutarse exponencialmente en el parámetro k. Pero en la práctica, todas las reducciones de FPT que he visto son reducciones de tiempo p, lo que significa que las pruebas de dureza W [t] casi siempre implican pruebas de integridad de NP.
Me pregunto si alguien puede darme una reducción de FPT que de hecho se ejecute exponencialmente en el parámetro . Gracias.
El siguiente documento contiene reducciones para varias parametrizaciones de la subcadena más cercana donde el tiempo de ejecución depende exponencialmente o doblemente exponencialmente del parámetro (y esta dependencia parece ser inevitable).
D. Marx. Problemas de subcadena más cercanos con distancias pequeñas . SIAM Journal on Computing, 38 (4): 1382-1410, 2008.
fuente
Como complemento a las otras respuestas, la siguiente Proposición muestra que las nociones correspondientes de reducibilidad son incomparables:
[2]: J. Flum, M. Grohe. Teoría de la complejidad parametrizada. Springer (2006)
fuente
Probablemente esta no sea una respuesta prevista, pero ¿qué tal (una variante desrandomizada de) codificación de colores para el problema de k-path? http://en.wikipedia.org/wiki/Color-coding
Allí, uno transforma una instancia del problema k-path en instancias del problema colorido k-path mediante una reducción fpt con dependencia súper polinómica de k. (Uno crea múltiples instancias, pero pueden verse como una gran instancia). Dado que el problema colorido de k-path se puede resolver en tiempo fpt mediante programación dinámica, podemos concluir que el problema de k-path pertenece a FPT.
fuente
Otro ejemplo de tal reducción es la prueba de dureza para la dimensión VC. Ver "Complejidad de aprendizaje parametrizada" por Downey, Evans y Fellows.
fuente