Riduzione da VC a {A, K |A è un 3DNF (forma normale disgiuntiva) e esiste un incarico che soddisfa esattamente i clausole k in}

Question

Ho la seguente domanda:

\ begin {allinea} L_2={a, k \ \ mid \ text {A è un 3DNF (forma normale disgiuntiva) e} \\ \ text {esiste un incarico $ z $ soddisfacendo esattamente $ k $ clausole in} a \} \ end {allinea}

So che $ l_2 \ in $ NPC.

Mostra che $ l_2 \ in $ np è relativamente facile, salterò quella parte.

Cerco di mostrare che $ l_2 \ in $ NPC utilizzando una riduzione da VC $ \ leq_p l_2 $ (VC è il coperchio vertice che sappiamo nel suo NPC)

Ho definito la seguente funzione $ f $ :

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

Ho pensato a qualcosa del genere per ogni nodo $ i $ in $ G $ definisce a Letterale $ x_i $ e renderlo in formato 3DNF, $ A=BigVee (x_i \ wedge x_i \ wedge x_i) $ dove $ 1 \ leq i \ leq n $ dove $ n $ è il numero di Nodi in $ G $ . Possiamo definire quella seguente $ z $ tale che $ z $ Safifica esattamente $ k $ clausole, basta dare $ '1' $ Letterale $ x_i $ tale che il nodo $ i $ è nella VC e $ '0' $ altrimenti, così Tale $ z $ esiste.

Così facile da vedere che $ (G, k) \ in $ vc $ \ implica (a, k) \ in l_2 $ Poiché abbiamo mostrato esplicitamente tale $ z $ che salva esattamente $ k $ clausole.

Ma non sono sicuro che l'altro lato contiene $ (g, k) \ non \ in $ vc $ \ implica (a, k) \ non \ in l_2 $ Abbiamo dato un grafico che non ha una dimensione VC $ k $ ma penso dovuto al mio edificio di A ( $ A=BigVee (x_i \ wedge x_i \ wedge x_i) $ ) Possiamo trovare $ z $ che salva esattamente $ k $ clausole (in realtà possiamo trovare $ z $ SAFFICI $ X $ CLAUSE DOVE $ 1 \ LEQ X \ LEQ N $ DOWN- Contenitore "> $ N $ è il numero di nodi in $ G $ .

Quindi la mia riduzione non tiene?

Answer 1

La ragione del motivo per cui hai problemi è perché la tua soluzione non funziona. In particolare, il problema è che la tua formula non cattura l'istruzione del problema VC. Più precisamente, la formula che costruisci ha sempre compiti di soddisfare $ k $ clausole semplicemente impostando $ k $ Variabili per true e il resto a false.

Sia le consente $ g= (v, e) $ essere un grafico e $ x \ SOTETEQ V $ Sii un VC in $ G $ . Quindi per qualsiasi EDGE $ VW \ IN E $ Dobbiamo avere $ v \ in x $ o $ w \ in x $ , dandoci 3 possibilità reciprocamente esclusive (riscrivendo essenzialmente $ v \ vee w $ in DNF):

.
• $ v \ in x $ ma $ w \ notin x $ ,
• $ v \ notin x $ ma $ w \ in x $
• $ v \ in x $ e $ w \ in x $

Da qui il bordo $ VW $ è coperto da $ x $ se e solo se la formula < span class="math-container"> $ \ psi (vw)= (v \ wedge w) \ vee (\ neg v \ wedge w) \ vee (v \ wedge \ neg w w) $ ha esattamente uno clausola soddisfatta (sotto il compito corrispondente a $ x $ ).

Costruire una tale formula per ogni bordo e prendendo la loro disgiunzione, otteniamo la formula DNF $$ \ PSI ^ \ text {vc} (g)=bigvee_ {e \ in e} \ psi (e)=bigvee_ {vw \ in e} (v \ wedge w) \ vee (\ neg v \ wedge w) \ vee (v \ wedge \ neg w w) $$ e qualsiasi assegnazione che soddisfa esattamente $ | E | $ clausole deve essere un VC di $ G $ . Ora abbiamo bisogno di un modo per codificare le dimensioni del VC in tutto ciò, per il quale possiamo riutilizzare la tua idea. Definire $$ \ PSI (G)=PSI ^ \ testo {vc} (g) \ vee \ bigvee_ {v \ in v} v $$ e nota che il numero di clausole soddisfatte nella seconda parte è appena fornita dalla dimensione del set di vertici selezioniamo, quindi il numero totale di clausole soddisfatte nell'ambito dell'assegnazione corrispondente ad alcuni VC $ X $ in $ G $ è $ | E | + | X | $ .

C'è solo un problema che rimanga qui. Potremmo ottenere un incarico che non corrisponde a un VC ma includendo più vertici per soddisfare lo stesso numero di clausole che un VC desiderato lo farebbe. Come rimedio, possiamo ripetere la prima formula ad alcune $ | V | + 1 $ Tempi tali che non importa quanti vertici hai scelto, il numero totale di clausole soddisfatte sarà sempre troppo bassa.

quindi otteniamo la formula finale $$ \ PSI ^ \ AST (G)=BigVee_ {i= 1} ^ {I= 1} ^ {| V | + 1} \ PSI ^ \ text {vc} (g) \ vee \ bigvee_ {v \ in v} v $$ e nota che se $ G $ ha una VC $ x $ quindi l'assegnazione corrispondente soddisferà esattamente < Class="Math-Container"> $ (| V | + 1) \ cdot | e | + | X | $ clausole di $ \ psi ^ \ ast (g) $ . Per la direzione inversa, let $ \ alfa $ essere un po 'di assegnazione soddisfacente $ (| V | + 1) \ cdot | e | + k $ clausole di $ \ psi ^ \ ast (g) $ . Quindi $ \ alfa $ deve rappresentare un VC in g come altrimenti, il numero di clausole soddisfatte nella prima parte della $ \ PSI ^ \ AST (G) $ è al massimo $ (| V | + 1) \ cdot (| e | - 1)= | V | \ cdot | e | + | E | - | v | - 1 $ e come $ \ alfa $ può soddisfare al massimo $ | V | $ clausole nella seconda parte, il numero totale di clausole soddisfatte sarà al massimo $$ (| V | + 1) \ cdot (| e | - 1) + | v |= | V | \ cdot | e | + | E | - 1 <(| V | + 1) \ cdot | e | $$ Tuttavia, ciò implica che il numero totale di clausole soddisfatte nella prima parte deve essere esattamente $ (| V | + 1) \ cdot | e | $ e quindi esattamente < Span Class="Math-Container"> $ k $ Le clausole della seconda parte sono soddisfatte da $ \ alfa $ , quindi $ \ alfa $ corrisponde a una classe VC $ x_ \ alfa $ di taglia $ k $ in $ G $ .

Si noti che per chiarezza non ho specificato una $ 3 $ -DNF Formula. Tuttavia, come tutte le clausole in $ \ psi ^ \ ast (g) $ sono di dimensioni al massimo $ 2 $ puoi jus

t Aggiungi i letterali ridondanti alle clausole per soffiarli fino a Size $ 3 $ Se necessario.

Non sono sicuro che questo sia il modo migliore per farlo, ma dovrebbe funzionare.Ho omesso alcuni dettagli per Brevity, non esitate a chiedere chiarimenti aggiuntivi se qualcosa non è chiaro :)