reducción fácil desde 3SAT al problema del camino hamiltoniano

Question

Hay una reducción en el libro de Sipser "Introducción a la teoría de la computación" en la página 286 de 3SAT al problema del camino hamiltoniano.

¿Hay una reducción más simple?

Por más simple que quiero decir una reducción que sería más fácil de entender (para estudiantes).

¿Hay una reducción que los usos lineales número de variables?

La reducción en Sipser utiliza $ variables de O (kn) $ donde $ k $ es el número de cláusulas y $ n $ es el número de variables. En otras palabras, es posible que la reducción a soplar el tamaño de $ a $ O (s ^ 2) $ $ s. ¿Hay una simple reducción en el tamaño de la salida de la reducción es lineal en el tamaño de su entrada?

Si no es posible, ¿hay alguna razón? ¿Eso implica un resultado desconocido en la complejidad de los algoritmos /?

Answer 1

El número de vértices en la reducción conocida de 3SAT a Path hamiltoniano dirigida (dHAMPATH) se puede reducir fácilmente a $ O (n + k) $, donde $ n $ es el número de variables y $ k $ es el número de cláusulas, por lo tanto el tamaño de la instancia gráfica construida es lineal con el tamaño de la instancia 3SAT originales.

En la reducción original, hemos iniciar vértice y vértice final, $ k $ vértices de las cláusulas, las listas de $ n $ de longitud $ 4k $ para las variables. La idea es que no tenemos a la lista de constructo de longitud $ 4k $ para cada variable, podemos lista de construcción de acuerdo con el número que aparece en la variable de todas las cláusulas. Dado que el número total de apariciones de variables en cláusulas es $ 3k $, es $ O (n + k) $.