Teorema: 3SAT es NP-difícil. Prueba: – Se construye una f computable en tiempo polinómico tal que w ∈ CNF-SAT si f(w) ∈ 3SAT.