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 , donde es un alfabeto finito y es el conjunto de números no negativos. Por lo tanto, una instancia de un problema parametrizado es un par , donde es el parámetro.
Un problema parametrizado es un parámetro fijo reducible a un problema parametrizado si existen funciones , : , y un polinomio tal que para cualquier instancia de , es una instancia de computable en el tiempo y si y solo si . 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 [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 para el problema AGVC (por encima de la cubierta del vértice de garantía) [3], que es mejor que el algoritmo original [4].
¿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.
Respuestas:
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
Y N π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π1 nc
Y N
π1 π2
c π1 k n nc . 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