Conjetura: todos los lenguajes completos de FPT NP son isomorfos de parámetros fijos

10

Conjetura de Berman-Hartmanis: todos los lenguajes NP completos se parecen, en el sentido de que pueden estar relacionados entre sí por isomorfismos de tiempo polinomiales [1].

Estoy interesado en una versión más detallada del "tiempo polinómico", es decir, si usamos reducciones parametrizadas.

Un problema parametrizado es un subconjunto de Σ×Z0 , donde Σ es un alfabeto finito y Z0 es el conjunto de números no negativos. Por lo tanto, una instancia de un problema parametrizado es un par (I,k) , donde k es el parámetro.

Un problema parametrizado π1 es un parámetro fijo reducible a un problema parametrizado π2 si existen funciones f , g : Z0Z0 , Φ:Σ×Z0Σ y un polinomio p(·) tal que para cualquier instancia (I,k) de π1 , (Φ(I,k),g(k)) es una instancia de π2 computable en el tiempo f(k)·p(|I|) y (I,k)π1 si y solo si (Φ(I,k),g(k))π2 . Dos problemas parametrizados son equivalentes de parámetros fijos si son reducibles entre sí por parámetros fijos.

Algunos problemas NP-completos son FPT, por ejemplo, la versión de decisión del problema de cobertura de vértice es NP-Complete, tiene un O(1.2738k+kn) [2]. Encontrar mejores reducciones de parámetros fijos de un problema de FPT que es NP-Complete puede conducir a un mejor algoritmo, por ejemplo, al invocar una reducción a una "versión de garantía anterior" del problema de corte de múltiples vías puede conducir a un algoritmo en el tiempo O(4k) para el problema AGVC (por encima de la cubierta del vértice de garantía) [3], que es mejor que el algoritmo original O(15k) [4].

My Conjecture: All FPT NP-complete languages are fixed-parameter-isomorphic.

¿Es cierta esa conjetura?

[1] Berman, L .; Hartmanis, J. (1977), "Sobre isomorfismos y densidad de NP y otros conjuntos completos", SIAM Journal on Computing 6 (2): 305–322.

[2] J. Chen, IA Kanj y G. Xia, límites superiores mejorados para la cubierta de vértice, Theor.Comput. Sci., 411 (2010), págs. 3736-3756.

[3] M. Cygan, M. Pilipczuk, M. Pilipczuk y JO Wojtaszczyk, sobre corte de múltiples vías parametrizado por encima de los límites inferiores, en IPEC, 2011.

[4] M. Mahajan y V. Raman, Parametrización de los valores garantizados anteriores: Maxsat y maxcut, J. Algorithms, 31 (1999), pp. 335-354.

Rupei Xu
fuente
3
No entiendo lo que quiere decir con un "lenguaje completo FPT NP". No existe una noción natural de que un lenguaje en sí mismo sea FPT; la pregunta es si un par de idioma / parámetro es FPT.
Huck Bennett
44
Tenga en cuenta que una reducción de parámetros fijos puede resolver un problema de FPT y generar una instancia trivial Sí / No del problema objetivo.
Serge Gaspers

Respuestas:

7

Serge Gaspers ya mencionó por qué su conjetura es trivialmente cierta.
Sin embargo, de hecho, uno puede obtener isomorfismos de parámetros fijos de tiempo polinómico ,
que ahora me doy cuenta de que no es mucho menos trivial, ya que se aplica a cada
par ordenado de problemas FPT no triviales con una reducción en el sentido ordinario.


Supongamos que sea ​​un número entero mayor que el grado del algoritmo FPT para , y que y sean una instancia de sí y no respectivamente de . Lo siguiente será una reducción de parámetros fijos de tiempo polinómico de a :cπ1
YNπ2
π1π2

Pruebe el algoritmo FPT en para hasta pasos. Si eso da una respuesta, entonces envíe o como lo indica esa respuesta. De lo contrario, muestre el resultado de aplicar una reducción de tiempo polinomial ordinario de a . La corrección y el tiempo de ejecución polinomial son obvios. Dado que es mayor que el grado del algoritmo FPT para , es el caso de que para cada fija , solo hay finitamente muchas longitudes de entrada para las cuales el tiempo de ejecución máximo del algoritmo FPT no es menor queπ1nc
YN
π1π2


cπ1knnc . Por lo tanto, para cada fijo , la reducción anterior solo tiene muchas salidas. Por lo tanto, satisface su condición de parámetro fijo.k


fuente