Prueba de que 4 SAT es NP completo

Problema 4-SAT : 4-SAT es una generalización de 3-SAT (k-SAT es SAT donde cada cláusula tiene k o menos literales).

Declaración del problema : dada una fórmula f en forma normal conjuntiva (CNF) compuesta de cláusulas, cada una de cuatro literales, el problema es identificar si existe una asignación satisfactoria para la fórmula f .

Explicación : una instancia del problema es una entrada especificada para el problema. Una instancia del problema 4-SAT es una fórmula CNF, y la tarea es verificar si existe una asignación satisfactoria para la fórmula. Dado que un NP-Completo es un problema que está tanto en NP como en NP-difícil , la prueba de la afirmación de que un problema es NP-Completo consta de dos partes:

1. El problema en sí está en la clase NP.
2. Todos los demás problemas en la clase NP pueden ser reducibles en tiempo polinomial a eso.
   (B es reducible en tiempo polinomial a C se denota como B ≤ P ^C )

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, simplemente 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 ≤ ^C . Para C en NP, entonces C es NP-Completo. Por lo tanto, se puede verificar que el Problema 4-SAT es NP-Completo usando las siguientes dos proposiciones:

1. 4-El problema SAT está en NP :
   si algún problema está en NP, entonces, dado un ‘certificado’, que es una solución al problema y una instancia del problema (una fórmula f , en este caso), se puede verificar (verifique si la solución dada es correcta o no) que el certificado en tiempo polinomial. Esto se puede hacer de la siguiente manera:
   Dada una asignación para las variables pertenecientes a la fórmula f , la asignación se puede verificar en tiempo lineal, si satisface o no la fórmula.
2. El problema 4-SAT es NP-Difícil :
   Para probar que el problema 4-SAT es NP-Difícil, deduzca una reducción de un problema NP-Difícil conocido a este problema. Deduzca una reducción a partir de la cual el problema 3-SAT se pueda reducir al problema 4-SAT. Para cada cláusula de lafórmula 3-SAT f , por ejemplo, se debe agregar a la fórmulaun literal a y su correspondiente complemento a’ . Sea una cláusula c , tal que c = u V v’ V w  
   Para convertirla en 4-SAT, convertimos c en c’ , tal que,  
   c’ = (u V v’ V w V a) Y ( uVv’VwVa’) . 
   Después de simular esta conversión, se cumplen dos propiedades:
   1. Si 3-SAT tiene una asignación satisfactoria, lo que significa que cada cláusula se evalúa como verdadera para un conjunto específico de valores literales, entonces 4-SAT también se cumplirá, porque cada conjunto de cláusulas está formado por una combinación de un literal y su complemento, cuyo valor no hará ninguna diferencia.
   2. Si 4-SAT es satisfacible para cualquier (u V v V w V a) y (u V v V w V a’) , entonces 3-SAT también es satisfacible porque a y a’ son complementarios, lo que indica que la fórmula es satisfacible debido a algún otro literal excepto a también.  

Por tanto, siguiendo las proposiciones anteriores, el problema 4-SAT es NP-Completo .