Réduction de VC à {A, K |A est une forme normale de 3DNF (une forme normale disjonctive) et il existe une affectation satisfaisant exactement k clauses dans un}

Question

J'ai la question suivante:

\ commence {align} L_2={A, k \ \ mid \ text {A est une forme normale de 3DNF (formulaire normale disjonctive) et} \\ \ TEXT {Il existe une affectation $ z $ Satisfait exactement K $ clauses de} a \} \ fin {align}

Je sais que $ l_2 \ in $ npc.

montre que $ l_2 \ in $ np est relativement facile, je vais ignorer cette partie.

J'essaie de montrer que $ l_2 \ in $ npc à l'aide d'une réduction de VC $ \ LEQ_P l_2 $ (VC est la couverture de sommet que nous connaissons dans son NPC)

J'ai défini la fonction suivante $ f $ :

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

J'ai pensé à quelque chose comme ça pour chaque nœud $ i $ in $ g $ définira un littéral $ x_i $ et le faire en format 3DNF, $ a=gigvee (x_i \ wedge x_i \ wedge x_i) $ où $ 1 \ leq i \ leq n $ où $ n $ est le nombre de nœuds dans $ g $ . Nous pouvons définir ce suivant $ z $ telle que $ z $ sflifie exactement $ K $ clauses, donnez simplement $ '1' $ '$ littéral $ x_i $ tel que le nœud $ i $ est dans la VC, et $ '0' $ sinon, alors telle $ z $ existe.

si facile de voir que $ (g, k) \ in $ vc $ \ implique (a, k) \ in l_2 $ puisque nous avons montré explicitement telle $ z $ qui confère exactement $ k $ clauses.

Mais je ne suis pas sûr que l'autre côté contienne $ (g, k) \ pas \ in $ in $ vc $ \ implique (a, k) \ pas \ in l_2 $ nous avons donné un graphique qui n'a pas de graphe de taille $ k $ mais je pense que à mon bâtiment d'un ( $ a=bigvee (x_i \ wedge x_i \ wedge x_i) $ ) nous pouvons trouver $ z $ qui confère exactement $ K $ clauses (en fait, nous pouvons trouver $ z $ que Safifie $ x $ $ clauses où $ 1 \ leq x \ Leq n $ où $ n $ est le nombre de nœuds dans $ g $ .

Donc, ma réduction ne contient pas?

Answer 1

La raison pour laquelle vous avez des problèmes, c'est parce que votre solution ne fonctionne pas. En particulier, le problème est que votre formule ne capture pas la déclaration de problème VC. Plus précisément, la formule que vous construisez toujours a des affectations satisfaisantes $ K $ clauses en définissant simplement $ k $ variables à vrai et le reste à faux.

alors laissez $ g= (v, e) $ être un graphique et $ x \ sous -éréq v $ Soyez un VC dans $ G $ . Ensuite, pour n'importe quel bord $ vw \ in e $ Nous devons avoir $ v \ in x $ ou $ w \ en x $ , donnant 3 possibilités mutuellement exclusives (en réécriture essentiellement $ v \ vee w $ DNF):

• $ v \ in x £ mais $ w \ notin x $
,
• $ v \ notin x $ mais $ w \ in x $
• $ v \ in x $ et $ w \ in x

d'où le bord $ VW $ est couvert par $ x $ si et seulement si la formule < SPAN CLASS="MATH-CONTENEUR"> $ \ PSI (VW)= (v \ wedge w) \ VEE (\ NEG V \ wedge w) \ vee (v \ wedge \ nge w) $ a exactement un Clause satisfaite (sous l'affectation correspondant à $ x $ ).

Construire une telle formule pour chaque bord et prendre leur disjonction, nous obtenons la formule DNF $$ \ psi ^ \ texte {vc} (g)=bigvee_ {e \ in e} \ psi (e)=bigvee_ {vw \ in e} (v \ coin w) \ vee (\ neg v \ wedge w) \ vee (v \ wedge \ nge w) $$ et toute mission satisfaisant exactement $ | e | $ clauses doit être une VC de $ g $ . Maintenant, nous avons besoin d'un moyen d'encoder la taille de la VC dans tout ce que nous pouvons réutiliser votre idée. Définir $$ \ psi (g)=psi ^ \ texte {vc} (g) \ vee \ bigvee_ {v \ in v} v $$ et notez que le nombre de clauses satisfaites dans la deuxième partie est uniquement donnée par la taille de l'ensemble des sommets que nous sélectionnons, de sorte que le nombre total de clauses satisfaites sous l'affectation correspondant à une VC $ X $ in $ g $ est $ | e | + | X | $ .

Il n'y a qu'un seul problème à rester ici. Nous pourrions avoir une mission ne correspondant pas à une VC mais y compris plus de sommets pour satisfaire le même nombre de clauses qu'un VC souhaité. En tant que remède, nous pouvons répéter la première formule certains $ | v | + 1 $ fois tel que peu importe le nombre de sommets que vous avez choisis, le nombre total de clauses satisfaites sera toujours trop faible.

Par conséquent, nous obtenons la formule finale $$ \ psi ^ \ ast (g)=bigvee_ {i= 1} ^ {| v | + 1} \ psi ^ \ texte {VC} (g) \ vee \ bigvee_ {v \ in v} v $$ et Notez que si $ g $ a une VC $ x $ alors que l'affectation correspondante satisfera exactement $ (| V | + 1) \ CDOT | E | + | X | $ clauses de $ \ psi ^ \ ast (g) $ . Pour la direction inverse, laissez $ \ alpha $ être une mission satisfaisante satisfaisant $ (| v | + 1) \ CDOT | e | + K $ clauses de $ \ psi ^ \ ast (g) $ . Alors $ \ alpha $ doit représenter une VC dans g comme autrement, le nombre de clauses satisfaites dans la première partie de $ \ PSI ^ \ ast (g) $ est au plus $ (| v | + 1) \ CDOT (| e | - 1)= | v | \ CDOT | E | + | E | - | v | - 1 $ et comme $ \ alpha $ peut satisfaire au plus $ | $ $ clauses dans la deuxième partie, le nombre total de clauses satisfaites sera au plus $$ (| v | + 1) \ CDOT (| E | - 1) + | v |= | V | \ CDOT | E | + | E | - 1 <(| V | + 1) \ CDOT | E | $$ Cependant, cela implique que le nombre total de clauses satisfaites dans la première partie doit être exactement $ (| v | + 1) \ CDOT | E | $ et donc exactement < SPAN CLASS="MATH-CONTENEUR"> $ K $ Les clauses de la deuxième partie sont satisfaites par $ \ alpha $ , donc $ \ alpha $ correspond à une VC $ x_ \ alpha $ de taille $ k $ dans $ g $ .

Notez que pour plus de clarté, je n'ai pas spécifié de 3 $ -DNF formule. Cependant, comme toutes les clauses de $ \ psi ^ \ ast (g) $ sont de taille au plus $ 2 $ vous pouvez jus

t Ajouter des littéraux redondants aux clauses pour les souffler jusqu'à la taille $ 3 $ si besoin d'être.

Je ne suis pas sûr que c'est la meilleure façon de le faire, mais cela devrait s'entraîner.J'ai omis quelques détails pour la brièveté, n'hésitez pas à demander des éclaircissements supplémentaires si quelque chose ne vous est pas clair :)