Prueba de que el camino hamiltoniano es NP-Completo

Prerrequisito: NP-Completeness La clase de lenguajes para los cuales la membresía puede decidirse rápidamente cae en la clase de P y La clase de lenguajes para los cuales la membresía puede verificarse rápidamente cae en la clase de NP ( significa problema resuelto en Turing no determinista Máquina en tiempo polinomial ). En palabras claras, cada problema NP tiene su propio verificador de tiempo polinomial. Un verificador para un lenguaje A es un algoritmo V, donde

A = {w | V accepts (w, c) for some string c}
where c is certificate or proof that w is a member of A.

Estamos interesados en problemas NP-Completos. El problema NP-Completo se define de la siguiente manera:

(1)The problem itself is in NP class.
(2)All other problems in NP class can be polynomial time reducible to that.
(B is polynomial time reducible to C is denoted as )

Si solo se cumple la segunda condición, el problema se llama NP-Hard. Pero no es posible reducir cada problema NP a otro problema NP para mostrar su NP-Completitud todo el tiempo. Es por eso que si queremos mostrar que un problema es NP-Completo, solo mostramos que el problema está en NP y cualquier problema NP-Completo es reducible a eso, entonces hemos terminado, es decir, si B es NP-Completo y $B$\leqslant_P$C$ para C en NP , entonces C es NP-Completo. Tenemos que mostrar que el camino hamiltoniano es NP-Completo. El camino hamiltoniano o HAMPATH en un gráfico dirigido G es un camino dirigido que pasa por cada Node exactamente una vez. Consideramos el problema de probar si un gráfico dirigido contiene una ruta hamiltoniana que conecta dos Nodes específicos, es decir

HAMPATH = {(G, s, t) | G is directed graph with a Hamiltonian path from s to t}

Para probar que HAMPATH es NP-Completo tenemos que probar que HAMPATH está en NP. Para demostrar que HAMPATH está en NP, debemos tener un verificador de tiempo polinomial. Aunque no tenemos un algoritmo de tiempo polinomial rápido para determinar si un gráfico contiene un HAMPATH o no, si se descubre esa ruta de alguna manera (tal vez con una búsqueda de fuerza bruta en tiempo exponencial) podríamos averiguar fácilmente si la ruta es HAMPATH o no, en tiempo polinomial. Aquí, el certificado será un camino hamiltoniano desde s hasta t en G, si existe. Entonces HAMPATH está en NP probado. Entonces, ahora tenemos que mostrar que cada problema de la clase NP es polinomial reducible en tiempo a HAMPATH para mostrar su NP-Completo. Más bien, mostraremos que 3SAT (un problema NP-Completo probado previamente a partir de SAT (problema de satisfacción del circuito)) es un tiempo polinomial reducible a HAMPATH. Convertiremos un dadocnf (forma normal conjuntiva) forma un gráfico donde los gadgets (estructura para simular variables y cláusulas) imitarán las variables y cláusulas (varios literales o variables conectadas con $\vee$ ). Tenemos que probar ahora $3SAT$\leqslant_P$HAMPATH$ . Para cada fórmula de 3 cnf $$$\Phi$ , mostraremos cómo construir el gráfico G con s y t, donde existe un camino hamiltoniano entre s y t iff $\Phi$ es satisfactorio. Empezamos con una fórmula de 3 cnf que $\Phi$ contiene k cláusulas,

donde cada uno $a_i, b_i, c_i$ es un literal $x_i$ o $\bar{x_i}$ . Sean $x_1, x_2, ...x_l$ las l variables de $\phi$ . Ahora mostramos cómo convertir $\phi$ a un gráfico G. El gráfico G que construimos tiene varias partes para representar las variables y cláusulas que aparecen en $\phi$ . Representamos cada variable $x_i$ con una estructura en forma de diamante que contiene una fila horizontal de Nodes como se muestra en la siguiente figura. Especificamos el número de Nodes que aparecen en la fila horizontal más adelante. La siguiente figura representa la estructura global de G. Muestra todos los elementos de G y sus relaciones, excepto los bordes que representan la relación de las variables con las cláusulas que las contienen.Cada estructura de diamante contiene una fila horizontal de Nodes conectados por bordes que corren en ambas direcciones. La fila horizontal contiene 2k Nodes (como 2 Nodes para cada cláusula) más k-1 Nodes adicionales entre cada dos Nodes para una cláusula más 2 Nodes en los extremos que pertenecen a los rombos; 3k+1 Nodes totales. El siguiente diagrama da una imagen clara. Si la variable $x_i$ aparece en la cláusula $c_j$ , agregamos los siguientes dos bordes del j-ésimo par en el i-ésimo rombo al Node de la cláusula j-ésimo. Si $\bar{x_i}$ aparece en la cláusula c_j, agregamos dos aristas del j-ésimo par en el i-ésimo rombo al Node de la cláusula j-ésimo, como en la siguiente figura. Después sumamos todas las aristas correspondientes a cada ocurrencia de $x_i$ o $\bar{x_i}$ en cada cláusula, la construcción de G está completa. Para mostrar su corrección probaremos si $\phi$ es satisfecha, existe un camino hamiltoniano de s a t y viceversa, si tal camino existe $\phi$ es satisfiable. Supongamos que $\phi$ es satisfacible. Para demostrar un camino hamiltoniano de s a t, primero ignoramos los Nodes de la cláusula. El camino comienza en s, pasa por cada diamante y termina en t. Para golpear los Nodes horizontales en un diamante. el camino zigzaguea de izquierda a derecha o zigzaguea de derecha a izquierda; la asignación satisfactoria a $\phi$ determina si $x_i$ se asigna VERDADERO o FALSO respectivamente. Mostramos ambos casos en la siguiente figura.

Hasta ahora, este camino cubre todos los Nodes en G excepto los Nodes de cláusula. Podemos incluirlos fácilmente agregando desvíos en los Nodes horizontales. En cada cláusula, seleccionamos uno de los literales asignados como VERDADERO, al satisfacer la asignación. Si seleccionamos $x_i$ en la cláusula $c_j$ , podemos desviarnos en el j-ésimo par en el i-ésimo rombo. Hacerlo es posible porque $x_i$ debe ser VERDADERO, por lo que el camino zigzaguea de izquierda a derecha a través del rombo correspondiente. Por lo tanto, los bordes del $c_j$ Node están en el orden correcto para permitir un desvío y un regreso. De manera similar, si seleccionamos $\bar{x_i}$ en la cláusula $c_j$ , podemos desviarnos en el j-ésimo par en el i-ésimo rombo porque $x_i$ debe ser FALSO, por lo que el camino zigzaguea de derecha a izquierda a través del rombo correspondiente. De ahí los bordes a él $c_j$ Node están nuevamente en el orden correcto para permitir un desvío y regreso. Cada vez que se toma un desvío si cada literal en la cláusula proporciona una opción para el desvío. Por lo tanto, cada Node se visita exactamente una vez y, por lo tanto, se construye el camino hamiltoniano. Para la dirección inversa, si G tiene un camino hamiltoniano de s a t, demostramos una asignación satisfactoria para $\phi$ . Si el camino hamiltoniano es normal, es decir, atraviesa rombos en orden desde el Node superior al inferior excepto el desvío para los Nodes de cierre; podemos obtener fácilmente la asignación satisfactoria. Si el camino zigzaguea en diamante, asignamos las variables como VERDADERO y si zigzaguea, lo asignamos FALSO. Debido a que cada Node aparece en el camino al observar cómo se toma el desvío, podemos determinar las variables VERDADERAS correspondientes. Todo lo que queda por demostrar es que el camino hamiltoniano debe ser normal significa que el camino entra en una cláusula desde un rombo pero regresa a otro como en la siguiente figura.

El camino va del Node $a_1$ a c; pero en lugar de volver a $a_2$ en el mismo diamante, vuelve a $b_2$ en el diamante diferente. Si eso ocurre, entonces $a_2$ o $a_3$ debe ser un Node separador. Si $a_2$ fuera un Node separador, los únicos bordes $a_2$ que entrarían serían desde $a_1$ o $a_3$ . Si $a_3$ fuera un Node separador entonces $a_1$ y $a_2$ estaría en la misma cláusula, entonces los bordes que entran $a_2$ desde $a_1$ y $a_3$ c. En cualquier caso, la ruta no puede ingresar porque solo hay un Node disponible al que $a_2$ apunta , por lo que la ruta debe salir a través de $a_3$ $a_3$ $a_2$ $a_2$ $a_3$ . Por lo tanto, el camino hamiltoniano debe ser normal. Esta reducción obviamente opera en tiempo polinomial y por lo tanto la prueba es completa de que HAMPATH es NP-Completo. Imágenes de referencia: https://tr.m.wikipedia.org/wiki/Hamilton_yolu