Reducción de VC a {A, K |a es un 3DNF (forma normal disyuntiva) y existe una asignación que satisface exactamente las cláusulas K en A}

Question

Tengo la siguiente pregunta:

\ comienzan {align} L_2={a, k \ \ medi-text {a es un 3DNF (forma normal disyuntiva) y} \\ \ Texto {Existe una asignación $ Z $ satisfactoria exactamente $ K $ cláusulas en} A \} \ End {align}

Sé que $ l_2 \ en $ NPC.

Muestra que $ l_2 \ en $ NP es relativamente fácil, omitiré esa parte.

Intento mostrar que $ l_2 \ en $ NPC utilizando una reducción de VC $ \ leq_p l_2 $ (VC es una cobertura de vértice que conocemos en su NPC)

Definimos la siguiente función $ f $ :

$$ f (g, k)= (a, k) $$

Pensé en algo así para cada nodo $ i $ en $ g $ definirá un Literal $ x_i $ y hazlo en formato 3DNF, $ a=bigvee (x_i \ wedge x_i \ wedge x_i) $ donde $ 1 \ leq i \ leq n $ donde $ n $ es el número de Nodos en $ g $ . Podemos definir ese siguiente $ z $ de tal que $ z $ safifies exactamente $ K $ cláusulas, solo dale $ '1' $ literal $ x_i $ tal que el nodo $ i $ está en la VC, y $ '0' $ de lo contrario, por lo que Tal $ z $ existe.

Tan fáciles de ver que $ (g, k) \ en $ vc $ \ implica (a, k) \ in l_2 $ Desde que mostramos explícitamente un $ z $ que se adapta exactamente $ k $ cláusulas.

Pero no estoy seguro de que el otro lado se mantiene $ (g, k) \ no \ in $ vc $ \ implica (a, k) \ no \ in l_2 $ Dio un gráfico que no tiene VC en tamaño $ k $ pero creo que debido a mi edificio de un ( $ a=bigvee (x_i \ wedge x_i \ wedge x_i) $ ) Podemos encontrar $ Z $ que safifies exactamente $ k $ cláusulas (en realidad podemos encontrar $ z $ que Safifies $ x $ cláusulas donde $ 1 \ leq x \ leq n $ donde $ n $ es el número de nodos en $ g $ .

¿Entonces mi reducción no se mantiene?

Answer 1

La razón por la que está teniendo problemas es porque su solución no funciona. En particular, el problema es que su fórmula no captura la declaración del problema de VC. Más precisamente, la fórmula que construyó siempre tiene asignaciones que satisfacen $ k $ cláusulas por el ajuste $ k $ variables Para verdaderos y el resto a falso.

así que deje $ g= (v, e) $ sea un gráfico y $ x \ subespeteq v $ Sé un VC en $ g $ . Luego, para cualquier borde $ vw \ in e $ debemos tener $ v \ in x $ o $ W \ in x $ , dándonos 3 posibilidades mutuamente exclusivas (mediante la reescritura esencialmente $ v \ vee w $ en DNF):

• $ v \ in x $ pero $ w \ notin x $ ,
• $ v \ notin x $ pero $ w \ in x $
• $ v \ in x $ y $ w \ in x $

De ahí el borde $ VW $ está cubierto por $ x $ si y solo si la fórmula < Span Class="Math-contenedor"> $ \ psi (vw)= (v \ wedge w) \ vee (\ neg v \ wedge w) \ vee (v \ wedge \ neg w) $ tiene exactamente uno Cláusula Satisfecha (bajo la asignación correspondiente a $ x $ ).

Construyendo tal fórmula para cada borde y tomando su disyunción, obtenemos la fórmula DNF $$ \ psi ^ \ texto {vc} (g)=bigvee_ {e \ in e} \ psi (e)=bigvee_ {vw \ in e} (v \ wedge w) \ vee (\ net v \ wedge w) \ vee (v \ wedge \ neg w) $$ y cualquier asignación que satisfaga exactamente $ | e | $ Las cláusulas deben ser un VC de $ g $ . Ahora necesitamos una forma de codificar el tamaño del VC en él, para lo cual podemos reutilizar su idea. Definir $$ \ psi (g)=psi ^ \ texto {vc} (g) \ vee \ bigvee_ {v \ in v} v $$ y tenga en cuenta que el número de cláusulas satisfechas en la segunda parte se presenta por el tamaño del conjunto de vértices que seleccionamos, por lo que el número total de cláusulas satisfechas en la asignación correspondiente a algunos VC $ X $ en $ g $ es $ | e | + | X | $ .

Solo hay un problema que permanece aquí. Podríamos obtener una tarea no correspondiente a un VC, pero incluyeron más vértices para satisfacer el mismo número de cláusulas que lo desea el VC deseado. Como remedio, podemos repetir la primera fórmula algunos $ | + 1 $ veces de manera que no importa cuántos vértices elegidos, el número total de cláusulas satisfechas siempre será demasiado bajo.

Por lo tanto, obtenemos la fórmula final. $$ \ PSI ^ \ AST (G)=bigvee_ {i= 1} ^ {| v | + 1} \ psi ^ \ texto {vc} (g) \ vee \ bigvee_ {v \ in v} v $$ y tenga en cuenta que si $ g $ tiene un vc $ x $ entonces la asignación correspondiente satisfará exactamente $ (| V | + 1) \ CDOT | E | + | X | $ cláusulas de $ \ psi ^ \ At (g) $ . Para la dirección inversa, deje que $ \ alfa $ sea alguna asignación satisfactoria $ (| v | + 1) \ cdot | e | + k $ cláusulas de $ \ psi ^ \ At (g) $ . Luego, $ \ alfa $ debe representar un VC en G como lo contrario, el número de cláusulas satisfechas en la primera parte de $ \ PSI ^ \ AST (G) $ está a la mayoría $ (| v | + 1) \ cdot (| e | - 1)= | v | \ CDOT | E | + | E | - | v | - 1 $ y como $ \ alfa $ puede satisfacer a la mayoría $ | v | $ cláusulas en la segunda parte, el número total de cláusulas satisfechas será como máximo $$ (| v | + 1) \ cdot (| e | - 1) + | v |= | V | \ CDOT | E | + | E | - 1 <(| v | + 1) \ CDOT | E | $$ Sin embargo, esto implica que el número total de cláusulas satisfechas en la primera parte debe ser exactamente $ (| v | + 1) \ cdot | e | $ y por lo tanto exactamente Span Class="Math-contenedor"> $ K $ Las cláusulas de la segunda parte están satisfechas por $ \ alfa $ , por lo $ \ alfa $ corresponde a un VC $ x_ \ alfa $ de tamaño $ k $ en $ g $ .

Tenga en cuenta que para mayor claridad, no especificé un $ 3 $ -dnf fórmula. Sin embargo, como todas las cláusulas en $ \ psi ^ \ ast (g) $ son de tamaño a la mayoría de $ 2 $ puedes jus

t Agregar literales redundantes a las cláusulas para soplarlas hasta el tamaño $ 3 $ si es necesario.

No estoy seguro de que esta sea la mejor manera de hacer esto, pero debería funcionar.Omití algunos detalles para la brevedad, no dude en solicitar aclaraciones adicionales si algo no está claro para usted :)