Ver el código de «Clase 2 (Especificación y Complejidad)»

=Temas vistos en la clase=

==Reduccion de SAT a 3-SAT==

Sea F = C1 ^ ... ^ Cn  conjunción de clausulas  (^ operador And)

Sea µi(Ci)= # literales de Ci 
  
Sea µ(F) = max{µi(Ci)}

Si pasa que µ(F)> 3 , reemplazamos F por F' con µ(F') < µ(F) en un procedimiento recursivo


Sea x nueva variable booleana y sin restriccion de generalidad µ(F)=µ1(C1) 

Entonces C1 = l1 v ... v ls con s>3  (li es un literal, v operador Or)

Defino 

 C1'  = l1 v l2 v x

 C1' ' = l3 v ... v ls v ¬x


Observacion: F es satisfacible sii F'= C1' ^ C1' ' ^ C2 ^ ... ^ Cn  es satisfacible

Demo: 
sea valuacion V , tal que V(F)=1

Entonces en particular V(C1)=1 , mas especificamente V(l1 v l2)=1 ó V(l3 v ... v ls)=1

Luego hay dos casos:

Si V(l1 v l2)=1 entonces defino V(x)=0

Sino, Si V(l3 v ... v ls)=1 entonces defino V(x)=1

Lo puedo hacer porque x es nueva y no afecta V(F)

En ambos casos vale V(C1')= V(C1' ')= 1, mantenemos satisfabilidad.

Y vale que µ(F')= µ(F)-1       ■



Para completar habria que demostrar que la longitud maxima de la clausula de F se baja a 3
en tiempo polinomial.

Segun Joos es O(│F│^2)