Dimostrazione riduzione 3CNF<= IS

[leadfoot]

salve, ho un grosso dubbio.
La dimostrazione per la riducibilità di una 3CNF <= IS come va scritta?
non è sufficiente tracciare il grafo?
C'è altro che deve essere formalizzato?
Grazie.

[Deckard1]

Definisci 'IS'.

[leadfoot]

"Deckard":Definisci 'IS'.

indipendent Set. un grafo non orientato i cui sono i letterali delle clausole .

Teorema Risulta che 3-CNF-SAT <= p IS.
Dim. Considera una qualunque 3-CNF φ (in forma normale
congiuntiva con k clausole ciascuna formata da esattamente
tre letterali). Costruisci da φ il seguente grafo
(non orientato):
1. i vertici sono definiti dalle occorrenze di letterali in φ
in modo che ad occorrenze distinte di letterali siano
associati vertici distinti;
2. ogni due letterali di una stessa clausola sono
adiacenti;
3. ogni due letterali complementari (xie ¬ xi in clausole
distinte) sono adiacenti.
Il grafo così costruito ammette un insieme indipendente
di dimensione almeno k se e solo se esiste un
assegnamento alle variabili che renda vera φ .
(fi) Infatti, se esiste un insieme indipendente I di
almeno k vertici, tale insieme non può contenere una
coppia di letterali che appartengono ad una stessa
clausola perché per costruzione essi sono adiacenti.
Poiché il numero di clausole è k, segue che I deve
consistere di esattamente k letterali. Inoltre, l’insieme
non può contenere letterali complementari (sia una
variabile che la sua negazione) altrimenti essi sarebbero
adiacenti.

tutto questo in modo formale.

[leadfoot]

se riesco posto qualcosa di mio. ma non so se sia corretto.

[hamming_burst]

"leadfoot":se riesco posto qualcosa di mio. ma non so se sia corretto.

prova a postare,
sulle "riduzioni" ho fatto poco, ma vediamo