Instancia de reducciones de FPT que no es una reducción de tiempo polinomial

11

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.k

yzll
fuente

Respuestas:

11

Un primer ejemplo es la prueba de dureza W [2] para el conjunto dominante del torneo (teorema 4.1 en [1]). La reducción es del conjunto dominante y construye un torneo con vértices , donde n es el número de vértices de la instancia del conjunto dominante yk es el parámetro.O(2kn)nk

[1]: Rodney G. Downey y Michael R. Fellows. Viabilidad computacional parametrizada. En P. Clote y JB Remmel, editores, Proceedings of Feasible Mathematics II, páginas 219-244. Birkhauser, 1995.

Serge Gaspers
fuente
1
Una prueba (tal vez diferente) de la misma afirmación también se puede encontrar en el libro "Teoría de la complejidad parametrizada" de J. Flum y M. Grohe, Teorema 7.17.
Mathieu Chapelle
8

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.

Daniel Marx
fuente
6

Como complemento a las otras respuestas, la siguiente Proposición muestra que las nociones correspondientes de reducibilidad son incomparables:

(Q,k)(Q,k)(Q,k)<fpt(Q,k)Q<ptime Q

<fpt<ptime

[2]: J. Flum, M. Grohe. Teoría de la complejidad parametrizada. Springer (2006)

Mathieu Chapelle
fuente
5

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.

Yoshio Okamoto
fuente
3

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.

Michael Lampis
fuente