Redução de VC a {a, k |A é um 3DNF (forma normal disjuntiva) e existe uma tarefa satisfazendo exatamente k cláusos em um}

Question

Eu tenho a seguinte pergunta:

\ begin {alinhar} L_2= {a, k \ \ mid \ text {a é um 3DNF (forma normal disjuntiva) e} \\ \ Texto {Existe uma tarefa $ Z $ satisfazendo exatamente $ k $ cláusulas em} a \} \ final {alinhar}

Eu sei que $ l_2 \ in $ npc.

Mostrar que $ l_2 \ in $ np é relativamente fácil, eu vou pular essa parte.

Eu tento mostrar que $ l_2 \ in $ npc usando uma redução do VC $ \ leq_p l_2 $ (VC é a cobertura do vértice que sabemos em seu NPC)

Eu defini a seguinte função $ F $ :

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

Eu pensei em algo assim para cada nó $ i $ em $ g $ definirá um literal $ x_i $ , e torná-lo no formato 3DNF, $ a=bigvee (x_i \ wedge x_i \ wedge x_i) $ onde $ 1 \ leq i \ leq n $ onde $ n $ é o número de nós na $ g $ . Podemos definir aquela seguinte $ z $ tal que $ z $ saffia exatamente $ K $ cláusulas, apenas dê $ '1' $ 1 '$ literal $ x_i $ De modo que o nó $ i $ está no VC, e $ '0' $ de outra forma, então tal $ z $ existe.

Tão fácil ver que $ (g, k) \ in $ vc $ \ implica (a, k) \ in l_2 $ desde que mostramos explicitamente tal $ z $ que protege exatamente $ k $ cláusulas.

Mas eu não tenho certeza que o outro lado detém $ (g, k) \ não \ in $ vc $ \ Implies (A, K) \ Not \ in l_2 $ Nós fornecidos um gráfico que não tem vc em tamanho $ k $ mas eu acho que devido Para o meu prédio de um ( $ a=bigvee (x_i \ wedge x_i \ wedge x_i) $ ) podemos encontrar $ z $ que protege exatamente $ k $ cláusulas (na verdade, podemos encontrar $ z $ que Safetiza $ x $ cláusulas onde $ 1 \ leq x \ leq n $ onde $ n $ é o número de nós em $ g $ .

Então, minha redução não é válida?

Answer 1

A razão para por que você está tendo problemas é porque sua solução não funciona. Em particular, o problema é que sua fórmula não captura a declaração do problema do VC. Mais precisamente, a fórmula que você constrói sempre tem tarefas satisfatórias $ k $ cláusulas simplesmente definindo $ k $ variáveis para verdade e o resto para falso.

Então, deixe $ g= (v, e) $ ser um gráfico e $ x \ subseteq v $ Seja um VC em $ g $ . Em seguida, para qualquer borda $ vw \ em e $ devemos ter $ v \ in x $ ou $ w \ em x $ , dando-nos 3 possibilidades mutuamente exclusivas (por essencialmente reescrevendo $ v \ Vee W $ em DNF):

• $ v \ em x $ mas $ w \ notin x $ ,
• $ v \ notin x $ mas $ w \ em x $
• $ v \ em x $ e $ w \ em x $

Portanto, a borda $ vw $ é coberta por $ x $ se e somente se a fórmula < span class="contentor de matemática"> $ \ psi (vw)= (vw)=Vee (\ Neg v \ Wedge W) \ Vee (v \ Wedge \ NEG W) $ tem exatamente um cláusula satisfeita (sob a tarefa correspondente à $ x $ ).

Construindo essa fórmula para cada borda e tomando sua disjunção, obtemos a fórmula DNF $$ \ psi ^ \ text {vc} (g)=bigvee_ {e \ in e} \ psi (e)=bigvee_ {vw \ em e} (v \ cunha w) \ Vee (\ Neg v \ Wedge W) \ Vee (v \ Wedge \ NEG W) $$ e qualquer tarefa satisfazendo exatamente $ | e | $ cláusulas deve ser um vc de $ g $ . Agora precisamos de uma maneira de codificar o tamanho do VC em tudo, para o qual podemos reutilizar sua ideia. Definir $$ \ psi (g)=psi ^ \ text {vc} (g) \ vee \ bigvee_ {v \ in v} v $$ e observe que o número de cláusulas satisfeitas na segunda parte é apenas dada pelo tamanho do conjunto de vértices que selecionamos, então o número total de cláusulas satisfeitas sob a atribuição correspondente a alguma VC $ X $ em $ g $ é $ | E | + | X | $ .

Há apenas um problema restante aqui. Poderíamos obter uma tarefa não correspondente a um VC, mas incluindo mais vértices para satisfazer o mesmo número de cláusulas que um VC desejado seria. Como remédio, podemos repetir a primeira fórmula que algumas $ | v | + 1 $ vezes tal que, não importa quantos vértices você escolhe, o número total de cláusulas satisfas sempre será muito baixa.

Por isso, obtemos a fórmula final $$ \ psi ^ \ AST (g)=bigvee_ {i= 1} ^ {| v | + 1} \ psi ^ \ text {vc} (g) \ vee \ bigvee_ {v \ in v} v $$ e observe que, se $ g $ tem uma VC $ x $ então a atribuição correspondente satisfará exatamente $ (| v | + 1) \ Cdot | E | + | X | $ cláusulas de $ \ psi ^ \ AST (g) $ . Para a direção inversa, deixe $ \ alfa $ ser alguma tarefa satisfatória $ (| v | + 1) \ Cdot | E | + k $ cláusulas de $ \ psi ^ \ AST (g) $ . Então $ \ alfa $ deve representar um vc em g de outra forma, o número de cláusulas satisfeitas na primeira parte da $ \ psi ^ \ AST (g) $ é no máximo $ (| v | + 1) \ Cdot (| E | - 1)= | v | \ Cdot | E | + | E | - | V | - 1 $ e como $ \ alfa $ pode satisfazer no máximo $ | v | $ cláusulas na segunda parte, o número total de cláusulas satisfeitas será no máximo $$ (| v | + 1) \ Cdot (| E | - 1) + | v |= | V | \ Cdot | E | + | E | - 1 <(| v | + 1) \ Cdot | E | $$ No entanto, isso implica que o número total de cláusulas satisfeitos na primeira parte deve ser exatamente $ (| v | + 1) \ Cdot | E | $ e, portanto, exatamente < span class="contentor de matemática"> $ k $ cláusulas da segunda parte são satisfeitos por $ \ alfa $ , então $ \ Alfa $ corresponde a uma VC $ x_ \ alfa $ de tamanho $ k $ em $ g $ .

Observe que, para Clarity, não especifiquei uma $ 3 $ -dnf fmula. No entanto, como todas as cláusulas em $ \ psi ^ \ AST (g) $ são de tamanho no máximo $ 2 $ você pode jus

T Adicione literais redundantes para as cláusulas para explodi-las até tamanho $ 3 $ se necessário.

Não tenho certeza de que esta é a melhor maneira de fazer isso, mas deve funcionar.Eu omitei alguns detalhes para brevidade, por favor, sinta-se à vontade para pedir esclarecimentos adicionais se algo não estiver claro para você :)