Partiamo da una formula CNF con clausole di lunghezza variabile, vogiamo generare un’istanza del 3SAT quindi avere solo clausole da 3 letterali in un numero di passi al più polinomniale Riduzione polinomiale. Per le clausole già di 3 letterali non devo fare niente, per quelle minori aggiungo copie dei letterali:
- Per 1 clausole:
Otteniamo una formula che è logicamente equivalente, indipendentemente dal valore di e , infatti se non esiste un assegnamento per le che rende vera la formula.
- Per 2 clasuole:
Ancora una volta otteniamo una formula logicamente equivalente, il valore di verità del letterale non influenza la formula.
- Per quelle più lunghe la questione è delicata, devo aggiungere nuove variabili dove è il numero di letterali della clausola ():
In questo caso non abbiamo una formula logicamente equivalente a quella di partenza, ma una formula che è soddisfacibile se e solo se quella di partenza lo è, che è quello che ci basta per il problema 3SAT.
Primo verso: se la clausola di partenza è UNSAT, allora tutti e letterali non sono messi a vero. Partendo dalla prima clausola, notiamo che deve valere , ma per costruzione vale la catena di implicazioni:
ma per rendere vera l’ultima clausola necessitiamo che .
Secondo verso: dato un assegnamento che soddisfa la clausola di partenza, si può estendere alle affinchè anche la formula ridotta sia soddisfatta. Senza perdità di generalità assumo che il letterale soddisfatto non compaia nelle clausole agli estremi (l’ordine dei letterali è arbitrario).
Un assegnamento che soddisfa la clausola di partenza deve mettere a vero almeno uno dei letterali , quindi la corrispondente clausola nella nuova formula è soddisfatta:
Abbiamo quindi piena libertà per i letterali e . Come prima in generale dobbiamo avere e . La differenza rispetto al primo caso è che la libertà di scelta dei letterali della clausola che contiene il letterale messo a vero ci permette di “spezzare” la catena di implicazioni, basta porre .